155. 最小栈

1. 题目

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

实现 MinStack 类:

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

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入：
["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.

提示：

  • -2^31 <= val <= 2^31 - 1
  • pop、top 和 getMin 操作总是在 非空栈 上调用
  • push, pop, top, and getMin最多被调用 3 * 10^4 次

2. 思路

  • 已知题目要求使用常量时间来检索到栈内最小的元素值，同时已知栈最多被调用 3 * 10 ^ 4次
  • 初始化stack数组和minStack数组，其中minStack数组用于记录递减的数值
  • 当执行push命令时，当minStack数组为空或当前推入栈的值小于等于minStack栈顶元素时。将值对应写入至minStack中
  • 当执行pop 命令时，如果推出的值与minStack的栈顶元素相同，同步推出minStack的栈顶元素
  • 当执行getMin命令时，只需要推出实时维护好的minStack栈顶元素
  • 由于栈的特性是先进先出，得益于该机制，可以使得minStack只需要关注递减序列即可

3. 代码

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
class MinStack {
    private int[] stack;
    private int[] minStack;
    private int index;
    private int minStackIndex;
    
    public MinStack() {
        this.stack = new int[3 * 10_000];
        this.minStack = new int[3 * 10_000];
        this.index = -1;
        this.minStackIndex = -1;
    }
    
    public void push(int val) {
        stack[++index] = val;
        if (minStackIndex == -1 || minStack[minStackIndex] >= val) {
            minStack[++minStackIndex] = val;
        }
    }
    
    public void pop() {
        if (stack[index] == minStack[minStackIndex]) {
            minStackIndex--;
        }
        index--;
    }
    
    public int top() {
        return stack[index];
    }
    
    public int getMin() {
        return minStack[minStackIndex];
    }
}

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

4. 复杂度

  • 时间复杂度：O(1)
  • 空间复杂度：O(n)

image-20230910231249464