题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

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

提示：

1. 各函数的调用总次数不超过 20000 次

题解

方法一：辅助栈

解题思路

普通栈的 push() 和 pop() 函数的复杂度为 O(1)，而获取栈最小值 min() 函数需要遍历整个栈，复杂度为 O(N)。

• 本题难点：将 min() 函数复杂度降为 O(1)，可通过建立辅助栈实现；

  • 数据栈 A：栈 A 用于存储所有元素，保证入栈 push() 函数、出栈 pop() 函数、获取栈顶 top() 函数的正常逻辑；
  • 辅助栈 B：栈 B 中存储栈 A 中所有 非严格降序 的元素，则栈 A 中的最小元素始终对应栈 B 的栈顶元素，即 min() 函数只需返回栈 B 的栈顶元素即可。

• 因此，只需设法维护好栈 B 的元素，使其保持非严格降序，即可实现 min() 函数的 O(1) 复杂度。

函数设计：

• push(x) 函数：重点为保持栈 B 的元素是 非严格降序 的。

  1. 将 x 压入栈 A（即 A.add(x)）；
  2. 若 ① 栈 B 为空 或 ② x 小于等于 栈 B 的栈顶元素，则将 x 压入栈 B（即 B.add(x)）。

• pop() 函数：重点为保持栈 A B 的 元素一致性。

  1. 执行栈 A 出栈（即 A.pop()），将出栈元素记为 y；
  2. 若 y 等于栈 B 的栈顶元素，则执行栈 B 出栈（即 B.pop()）。

• top() 函数：直接返回栈 A 的栈顶元素即可，即返回 A.peek()。

• min() 函数：直接返回栈 B 的栈顶元素即可，即返回 B.peek()。

代码

Java 代码中，由于 Stack 中存储的是 int 的包装类 Integer，因此需要使用 equals() 代替 == 来比较值是否相等。

class MinStack {
    Stack<Integer> A, B;
    public MinStack() {
        A = new Stack<>();
        B = new Stack<>();
    }
    public void push(int x) {
        A.add(x);
        if(B.empty() || B.peek() >= x)
            B.add(x);
    }
    public void pop() {
        if(A.pop().equals(B.peek()))
            B.pop();
    }
    public int top() {
        return A.peek();
    }
    public int min() {
        return B.peek();
    }
}

复杂度分析

• 时间复杂度 O(1) ：push()，pop()，top()，min() 四个函数的时间复杂度均为常数级别。
• 空间复杂度 O(N) ：当共有 N 个待入栈元素时，辅助栈 B 最差情况下存储 N 个元素，使用 O(N) 额外空间。

个人理解

1. 比较两个值相等一定要用 equals() 方法，因为 Stack 中存的是 Integer，不能用 == 来判断相等。
2. 元素一致性：上面代码中已经有了处理元素一致性的方法，就是在 A 栈中 pop 出来的元素，如果和 B 栈的栈顶元素相等，则将 B 栈的栈顶元素也 pop 出来。我们来看一下为什么这么做可以保证元素一致性。
   1. B 栈是非严格递减的，也就是说，在向 A 栈内添加元素的时候，如果后面的一个元素大于前面一个元素，是不会将元素压入 B 栈中的。
   2. 这就避免了我在 A 栈中弹出一个元素，结果在 B 栈中存在，但是不在栈顶，导致最后 B 栈元素不空等各种问题。因为我根本不会将大值压入 B 栈中。所以只需要比较栈顶元素即可，非严格递减存储的。
   3. 为什么这样可以，假设压入 A 栈中第一个元素是最小的，那么 B 栈只会有一个元素，整个过程中最小元素都是第一个，直到 A 中 pop 出最后一个元素。

方法二：我的解法

我是借鉴了上面的解法，不过我使用的是 Deque，因为 Stack 已经不推荐使用了。

class MinStack {

    Deque<Integer> A,B;

    /** initialize your data structure here. */
    public MinStack() {
        A = new LinkedList<>();
        B = new LinkedList<>();
    }

    public void push(int x) {
        A.addFirst(x);
        if (B.isEmpty() ||  x <= B.peekFirst()) {
            B.addFirst(x);
        }
    }

    public void pop() {
        if (A.removeFirst().equals(B.peekFirst())) {
            B.removeFirst();
        }
    }

    public int top() {
        return A.peekFirst();
    }

    public int min() {
        return B.peekFirst();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

题解来源

作者：jyd
链接：leetcode-cn.com/problems/bao-han-m...
来源：力扣（LeetCode）

题目来源

来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/bao-han-m...

本作品采用《CC 协议》，转载必须注明作者和本文链接