设计一个数据结构以支持堆栈操作并找到最小值

您可以通过维护两个堆栈来完成此操作

stack -在这个堆栈上执行常见的推和弹出操作。

minStack -此堆栈用于获取堆栈中的最小元素 O(1) 时间。在任何时候,这个堆栈的顶部元素都是堆栈中所有元素的最小值。

push( item a) 
    // push the element on the stack.
    stack.push(a)   

    // find the min of the ele to be pushed and the ele on top of minStack.
    if(minStack.isEmpty()) 
        min = a
    else
        min = Min(a,minStack.top())

    // push the min ele on the minStack.
    minStack.push(min) 
end push


pop()
    // pop and discard
    minStack.pop() 

    // pop and return
    return stack.pop() 
end pop


findMin()
    return minStack.top()
end findMin

在上面的解决方案中,每次将元素推到堆栈上时,都会有相应的推送 小堆 . 所以在任何时候,栈中元素的数量 小堆 是一样的。我们可以通过将元素推到 明斯塔克 只有当元素小于当前最小值时。

push( item a) 
    // push the element on the orginal stack.
    stack.push(a)   

    if(minStack.isEmpty())
            // if minStack is empty push.
            minStack.push(a) 
    // else push only if the element is less than or equal to the present min.
    else if(a <= minStack.top()) 
        minStack.push(a)
end push

pop()
    // pop from the stack
    ele = stack.top()     
    if(minStack.top() == ele)
            // pop only if the top element is ele.
        minStack.pop() 

    // return the popped element.
    return ele 
end pop

为此,您的数据结构应该包含两个堆栈。一个应该正常工作;另一个只包含看到的最后一个最小元素。当您推送一个元素时,如果它小于/等于第二个堆栈的顶部(或者堆栈为空),也可以推送到第二个堆栈。当弹出一个元素时,如果它等于第二个堆栈的顶部,则也会弹出第二个堆栈。

在任何时候,最小值都是第二个堆栈的顶部。

这个问题实际上是在问 Heap

PriorityQueue是一个经典的案例(堆的实现)。见 java.util.PriorityQueue

我希望在线上有一个简单的方法来引用Java语言源代码,在这里我可以看到并引用PrimyRealQueE类的实现。

在不使用辅助堆栈的情况下,有一个更具创造性的解决方案。

假设我们要推一个数字 价值 以最小的数目放入堆栈 闽 . 如果 价值 大于或等于 闽 将其直接推送到数据堆栈中。如果小于 闽 ,我们推2**值*- 闽 和更新 闽 作为 价值 因为一个新的最小数字被推。

去流行音乐怎么样?如果数据堆栈的顶部(它表示为 顶部 )大于或等于 最小 . 否则号码 顶部 不是真正的推送号码。实际推送的号码存储为 最小 . 弹出当前最小数后,需要恢复前一个最小数,即2**分钟*- 顶部 .

现在让我们演示一下这个解决方案的正确性。什么时候? 价值 大于或等于 闽 ,它被直接推入数据栈而不更新 闽 .因此,当我们发现数据栈的顶部大于或等于 闽 ,我们可以直接弹出而不更新 闽 . 但是,如果我们发现 价值 那么少 闽 我们推2 值** 闽 . 我们应该注意到2 值** 闽 小于 价值 . 然后我们更新当前 闽 作为 价值 . 因此,新的数据栈顶部( 顶部 )小于当前值 闽 .因此,当我们发现数据堆栈的顶部小于 闽 ,真正的顶部(真正的推送数字 价值 )存储在 闽 . 在我们弹出数据栈的顶部之后,我们必须恢复以前的最小值。自从 顶部 =2**值*-上一个 闽 和 价值 是电流 闽 透水性的 闽 是2*电流 闽 - 顶部 .

C++示例代码如下所示:

template <typename T> class StackWithMin {
public:
    StackWithMin(void) {}
    virtual ~StackWithMin(void) {}

    T& top(void);
    void push(const T& value);
    void pop(void);
    const T& min(void) const;

private:
    std::stack<T>   m_data;     // data stack, to store numbers
    T               m_min;      // minimum number
};

template <typename T> void StackWithMin<T>::push(const T& value) {
    if(m_data.size() == 0) {
        m_data.push(value);
        m_min = value;
    }
    else if(value >= m_min) {
        m_data.push(value);
    }
    else {
        m_data.push(2 * value - m_min);
        m_min = value;
    }
}

template <typename T> void StackWithMin<T>::pop() {
    assert(m_data.size() > 0);

    if(m_data.top() < m_min)
        m_min = 2 * m_min - m_data.top();

    m_data.pop();
}

template <typename T> const T& StackWithMin<T>::min() const {
    assert(m_data.size() > 0);

    return m_min;
}

template <typename T> T& StackWithMin<T>::top() {
    T top = m_data.top();
    if(top < m_min)
        top = m_min;

    return top;
}

此解决方案借用自 my blog 还有我的书 Coding Interviews: Questions, Analysis & Solutions “。