LeetCode 155. 最小栈 题解

题目

155. 最小栈

https://leetcode.cn/problems/min-stack/ https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof/

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

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

思路

我们找个用例看看:依次入栈-2 0 -3

1
2
3
4
5
6
7
8
[-2,0,-3]
对应最小值
[-2,-2,-3]
出栈-3

[-2,0]
对应最小值
[-2,0]

依次入栈0 1 0

1
2
3
4
5
6
7
8
[0,1,0]
对应最小值
[0,0,0]
出栈0

[0,1]
对应最小值
[0,0]

可以发现最小值需要一个容器维护,由于每次取出顺序与写入顺序相反,符合栈的性质。

使用另一个容器同步维护当前栈顶对应最小值

思路

我们尝试用一个栈存原数据,用另一个栈维护对应下标最小值。

两个栈的数据量保持一致。

复杂度分析

时间
  • push
    • stackFull 写入原数据
    • stackMini 写入 min(当前数据,stackMini.peek)
    • 基于数组或者链表的插入复杂度均为O(1)
  • pop
    • 出栈复杂度O(1)
  • getMini
    • 出栈复杂度O(1)
空间

使用了额外的栈维护对应最小值,空间占用O(n)

代码

 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
40
41
42
43
44
45
46
public class MinStack2 {

    /**
     * stackMini将局部最小值以与stackFull等量的方式存储
     */
    Stack<Integer> stackFull;
    Stack<Integer> stackMini;

    public MinStack2() {
        stackFull = new Stack<>();
        stackMini = new Stack<>();
    }

    public int pop() {
        Integer top = stackFull.pop();
        if (top == null) {
            throw new IllegalStateException();
        }
        stackMini.pop();
        return top;
    }

    public void push(int val) {
        stackFull.push(val);
        if (stackMini.isEmpty()) {
            stackMini.push(val);
        } else {
            Integer miniTop = stackMini.peek();
            int mini = val <= miniTop ? val : miniTop;
            stackMini.push(mini);
        }
    }

    public int getMin() {
        return stackMini.peek();
    }

    public int top() {
        return stackFull.peek();
    }

    public void clear() {
        stackFull.clear();
        stackMini.clear();
    }
}

这种思路下,我们可以有另外一种写法,使用一个栈维护出入栈操作,节点内部同步维护当前值、当前对应最小值。

 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
public class MinStack3 {

    Stack<int[]> stack;

    // 使用一个栈存储,内部存数据,0位存原数字,1位存对应最小值
    public MinStack3() {
        stack = new Stack<>();
    }

    public void push(int val) {
        if (stack.isEmpty()) {
            stack.push(new int[]{val, val});
        } else {
            int[] prev = stack.peek();
            int smaller = val < prev[1] ? val : prev[1];
            stack.push(new int[]{val, smaller});
        }
    }

    public int pop() {
        // 数组同步跟随stack出栈
        return stack.pop()[0];
    }

    public int getMin() {
        return stack.peek()[1];
    }

    public int top() {
        return stack.peek()[0];
    }

    public void clear() {
        stack.clear();
    }

}

使用另一个容器只维护当前写入更小的元素

思路

说起来有点拗口,解释起来就是,前面的做法我们的stackMini其实会存储与stackFull等数据量的数据,不难发现其中有很多值是重复的。

比如:

1
2
3
[0,1,2]
对应最小值
[0,0,0]

增量序列,其实我们只需要维护一个最小值即可。

也就是入栈出栈我们需要判断这个逻辑:

  • 递增序列:
    • 入栈:stackMini不入栈新数据,stackMini空则需要入栈;
    • 出栈:出到stackMini栈顶数据大小的时候,stackMini出栈
  • 递减序列:
    • 入栈:stackMini入栈新数据(因为新数据更小!!)
    • 出栈:因为出去的是比栈顶更小的数据,所以需要出栈,stackMini以此来追逐stackFull的步伐
  • 相等序列:
    • 入栈:stackMini也需要加入一个相同的元素,不加入后面出栈很难搞
    • 出栈:出到stackMini栈顶数据大小的时候,stackMini出栈

还需要把入栈出栈逻辑整理一下:

  • 入栈:
    • stackMini空则需要入栈;
    • 递增不入栈;
    • 递减、相等序列均入栈;
  • 出栈:
    • 出到stackMini栈顶数据大小的时候,stackMini出栈;

复杂度分析

同前方案。

代码

 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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public class MinStack {

    /**
     * 执行用时:
     * 4 ms
     * , 在所有 Java 提交中击败了
     * 93.20%
     * 的用户
     * 内存消耗:
     * 43.4 MB
     * , 在所有 Java 提交中击败了
     * 24.46%
     * 的用户
     * 通过测试用例:
     * 31 / 31
     */

    Deque<Integer> stackFull;
    // 存储局部最小元素
    Deque<Integer> stackMini;

    public MinStack() {
        stackFull = new LinkedList<>();
        stackMini = new LinkedList<>();
    }

    /**
     * stackFull 不管怎样,都要push
     * stackMini空,插入第一个最小元素,当前值小于mini顶,插入
     */
    public void push(int val) {
        stackFull.push(val);
        if (stackMini.isEmpty() || stackMini.peek() >= val) {
            stackMini.push(val);
        }
    }

    public int top() {
        if (stackFull.isEmpty()) {
            return -1;
        }
        return stackFull.peek();
    }

    public int pop() {
        Integer val = stackFull.pop();
        // 如果出栈了当前mini顶最小的元素,mini跟着出栈
        if (!stackMini.isEmpty() && stackMini.peek().equals(val)) {
            stackMini.pop();
        }
        return val == null ? -1 : val;
    }

    public int getMin() {
        if (stackMini.isEmpty()) {
            return -1;
        }
        return stackMini.peek();
    }

    public void clear() {
        stackFull.clear();
        stackMini.clear();
    }
}

这道题使用这种思路出错概率大一点。但是在n比较大规模的时候会节省不少空间。利弊参半。

Ref