多味的LeetCode --- 面试题 03.02. 栈的最小值

小咪咪 2023-02-18 08:19 34阅读 0赞

**题目描述：**

请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。

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

--------------------

**解题思路:**

开一个最小栈minstack，栈顶存放的是已经出现的最小元素。当压入的时候，比较需要压入的值x与栈顶的大小

--------------------

**代码：**

**python写法：**

class MinStack:
    
        def __init__(self):
            self.stack = []
            self.minstack = []
    
        def push(self, x):
            self.stack.append(x)
            if len(self.minstack) == 0 or x <= self.minstack[-1]:
                self.minstack.append(x)
    
        def pop(self):
            if self.stack.pop() == self.minstack[-1]:
                self.minstack.pop()
    
        def top(self):
            return self.stack[-1]
    
        def getMin(self):
            return self.minstack[-1]

--------------------

**c++写法：**

class MinStack {
        
    public:
        /** initialize your data structure here. */
        stack<int> stk, stk_min;
        MinStack() {
        
            
        }
        
        void push(int x) {
        
            stk.push(x);
            if (stk_min.empty()) stk_min.push(x);
            else stk_min.push(min(x, stk_min.top()));
        }
        
        void pop() {
        
            stk.pop();
            stk_min.pop();
        }
        
        int top() {
        
            return stk.top();
        }
        
        int getMin() {
        
            return stk_min.top();
        }
    };