leetcode热题HOT 155. 最小栈

一、问题描述：

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

二、解决方法：

1、思路分析：该最小栈使用两个栈来实现：一个普通的栈（stack）用于存储元素，另一个辅助栈（minStack）用于存储当前栈中的最小元素。

①在构造函数中，初始化两个栈，并在辅助栈中压入一个初始值 Integer.MAX_VALUE，保证了在初始状态下，最小栈的 getMin() 操作可以返回正确的最小值。
②push(int val) 方法将元素压入普通栈，并将当前栈中的最小值与新压入的值进行比较，将较小值压入辅助栈中，保持辅助栈的栈顶始终为当前栈中的最小元素。
③pop() 方法从普通栈中弹出元素，并同时从辅助栈中弹出对应的最小元素，以保持两个栈的同步。
④top() 方法直接返回普通栈的栈顶元素，而 getMin() 方法则返回辅助栈的栈顶元素，即当前栈中的最小元素。

2、代码示例

class MinStack {
    // 普通栈，用于存储元素
    Deque<Integer> stack;
    // 辅助栈，用于存储当前栈中的最小元素
    Deque<Integer> minStack;

    // 构造函数，初始化两个栈，并在辅助栈中压入一个初始值 Integer.MAX_VALUE
    public MinStack() {
        stack = new LinkedList<>();
        minStack = new LinkedList<>();
        minStack.push(Integer.MAX_VALUE);
    }
    
    // 元素入栈操作
    public void push(int val) {
        // 将元素压入普通栈
        stack.push(val);
        // 将当前栈中的最小值与新压入的值进行比较，并将较小值压入辅助栈中，保持辅助栈的栈顶始终为当前栈中的最小元素
        minStack.push(Math.min(minStack.peek(), val));
    }
    
    // 元素出栈操作
    public void pop() {
        // 从普通栈中弹出元素
        stack.pop();
        // 同时从辅助栈中弹出对应的最小元素，以保持两个栈的同步
        minStack.pop();
    }
    
    // 获取栈顶元素操作
    public int top() {
        // 直接返回普通栈的栈顶元素
        return stack.peek();
    }
    
    // 获取当前栈中的最小元素操作
    public int getMin() {
        // 返回辅助栈的栈顶元素，即当前栈中的最小元素
        return minStack.peek();
    }
}

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

3、 时间复杂度分析：

①push(int val) 方法的时间复杂度为 O(1)，因为它只是在两个栈中进行一些基本的操作，不会涉及遍历或循环。
②pop() 方法的时间复杂度也是 O(1)，因为它只是从两个栈中弹出元素，并没有涉及遍历或循环。
③top() 和 getMin() 方法也都是 O(1)，因为它们只是返回栈顶元素，并不会对栈中的元素进行修改或遍历。