leetcode 最小栈

落日映苍穹つ 2023-08-17 15:43 103阅读 0赞

> 设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

> push(x) -- 将元素 x 推入栈中。  
> pop() -- 删除栈顶的元素。  
> top() -- 获取栈顶元素。  
> getMin() -- 检索栈中的最小元素。  
> 示例:

> MinStack minStack = new MinStack();  
> minStack.push(-2);  
> minStack.push(0);  
> minStack.push(-3);  
> minStack.getMin(); --> 返回 -3.  
> minStack.pop();  
> minStack.top(); --> 返回 0.  
> minStack.getMin(); --> 返回 -2.

> 来源：力扣（LeetCode）  
> 链接：[https://leetcode-cn.com/problems/min-stack][https_leetcode-cn.com_problems_min-stack]

思路：设置一个存储值的栈和一个存储前i个数的最小值的栈，这里有一点需要注意，因为要删除值，那麽怎么让最小栈的元素删去呢，这里需要每次相等的元素也要加进来，并不是严格单调的。  
![image.png][]

比如如果我们不加入两个-3，那麽当我们删除stackvalue里的-3时，如何判断是不是该删除最小栈里的-3，我们固然可以先取出stackvalue的top然后再与top比较，相想等我们不删除stackmin里面的元素，但是我们可以不用这末麻烦，我们只需要再添加的时候，碰到<=stackmin.top()的元素都加进来，而不是只加比他小的,这样删除的时候只要stackvalue的top和stackmin的top相等就可以直接删除。

class MinStack {
    public:
        stack<int> stackvalue;
        stack<int> stackmin;
        MinStack() {
            
        }
        
        void push(int x) {
            stackvalue.push(x);
            if(stackmin.empty()||stackmin.top()>=x)
                stackmin.push(x);
        }
        
        void pop() {
            if(stackvalue.top()==stackmin.top())stackmin.pop();
            stackvalue.pop();
        }
        
        int top() {
            return stackvalue.top();
        }
        
        int getMin() {
            return stackmin.top();    
        }
    };

转载于:https://www.cnblogs.com/clear-love/p/11381554.html

[https_leetcode-cn.com_problems_min-stack]: https://leetcode-cn.com/problems/min-stack
[image.png]: /images/20230810/72a9ccfb17ed4ed2a49672a848ed2488.png