欢迎访问LeetCode题解合集

题目描述

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

• push(x) —— 将元素 x 推入栈中。

• pop() —— 删除栈顶的元素。

• top() —— 获取栈顶元素。

• getMin() —— 检索栈中的最小元素。

示例:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

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

提示：

• pop、top 和 getMin 操作总是在 非空栈 上调用。

题解：

法一：

使用两个栈。

核心思想就是确保最小值和栈顶元素一一对应。

一个栈 nums 保存元素，另一个栈 min_stk 维护最小值，从栈底到栈顶非严格单调递减。

在入栈时，如果 x > min_stk.top() ，说明最小值肯定不会是 x ；如果 x <= min_stk.top() ，此时需要把 x 加入 min_stk 中。

在出栈时，如果 nums.top() == min_stk.top() ，需要把 min_stk.top() 也出栈。

时间复杂度：$O(n)$

额外空间复杂度：$O(n)$

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() { }

    void push(int x) {
        nums.push( x );
        if ( !min_stk.size() || x <= min_stk.top() ) 
            min_stk.push( x );
    }

    void pop() {
        if( nums.top() == min_stk.top() ) min_stk.pop();
        nums.pop();
    }

    int top() {
        return nums.top();
    }

    int getMin() {
        return min_stk.top();
    }
private:
    stack<int> nums;
    stack<int> min_stk;
};
/*
时间：20ms，击败：97.24%
内存：15.5MB，击败：38.73%
*/

法二：

一个栈。

使用一个变量 min_val 记录最小值，依次将 x - min_val 入栈，如果 x - min_val < 0 ，说明出现了更小的值，更新最小值。

出栈时，如果 nums.top() < 0 ，此时需要恢复最小值 min_val = min_val - nums.top() 。

获取栈顶元素时，若 nums.top() < 0 ，栈顶元素就是 min_val ，否则是 min_val + nums.top() 。

注意：因为涉及到减法，可能会溢出，使用 long long 。

时间复杂度：$O(n)$

额外空间复杂度：$O(n)$

class MinStack {
    using L = long;
public:
    /** initialize your data structure here. */
    MinStack() { }

    void push(int x) {
        if ( !nums.size() ) {
            nums.push( 0 );
            min_val = x;
        } else {
            nums.push( x - min_val );
            if( x < min_val ) min_val = x;
        }
    }

    void pop() {
        if( nums.top() < 0 ) 
            min_val -= nums.top();
        nums.pop();
    }

    int top() {
        if( nums.top() < 0 ) return min_val;
        return min_val + nums.top();
    }

    int getMin() {
        return min_val;
    }
private:
    stack<L> nums;
    L min_val;
};
/*
时间：16ms，击败：99.58%
内存：15.5MB，击败：37.78%
*/

因为使用了 long long ，所以空间不一定省。。。