Leetcode 155 最小栈(Min Stack) 题解分析

发表于 分类于 ， ， ， ， 阅读次数： 阅读次数： Disqus：

题目介绍

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
设计一个栈，支持压栈，出站，获取栈顶元素，通过常数级复杂度获取栈中的最小元素

  • push(x) – Push element x onto stack.
  • pop() – Removes the element on top of the stack.
  • top() – Get the top element.
  • getMin() – Retrieve the minimum element in the stack.

示例

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

简要分析

其实现在大部分语言都自带类栈的数据结构，Java 也自带 stack 这个数据结构，所以这个题的主要难点的就是常数级的获取最小元素，最开始的想法是就一个栈外加一个记录最小值的变量就行了，但是仔细一想是不行的，因为随着元素被 pop 出去，这个最小值也可能需要梗着变化，就不太好判断了，所以后面是用了一个辅助栈。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class MinStack {
        // 这个作为主栈
        Stack<Integer> s1 = new Stack<>();
        // 这个作为辅助栈，放最小值的栈
        Stack<Integer> s2 = new Stack<>();
        /** initialize your data structure here. */
        public MinStack() {

        }

        public void push(int x) {
            // 放入主栈
            s1.push(x);
            // 当 s2 是空或者当前值是小于"等于" s2 栈顶时，压入辅助最小值的栈
            // 注意这里的"等于"非常必要，因为当最小值有多个的情况下，也需要压入栈，否则在 pop 的时候就会不对等
            if (s2.isEmpty() || x <= s2.peek()) {
                s2.push(x);
            }
        }

        public void pop() {
            // 首先就是主栈要 pop，然后就是第二个了，跟上面的"等于"很有关系，
            // 因为如果有两个最小值，如果前面等于的情况没有压栈，那这边相等的时候 pop 就会少一个了，可能就导致最小值不对了
            int x = s1.pop();
            if (x == s2.peek())  {
                s2.pop();
            }
        }

        public int top() {
            // 栈顶的元素
            return s1.peek();
        }

        public int getMin() {
            // 辅助最小栈的栈顶
            return s2.peek();
        }
    }