155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

  • MinStack() initializes the stack object.
  • void push(int val) pushes the element val onto the stack.
  • void pop() removes the element on the top of the stack.
  • int top() gets the top element of the stack.
  • int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

题目大意

设计一个支持 push（压栈）、pop（弹栈）、top（获取栈顶）、getMin（获取栈内最小值） 四种操作的栈，且要求 每个操作的时间复杂度均为 O (1)。

核心挑战：普通栈的 push/pop/top 可天然实现 O (1)，但 getMin 需突破 “遍历栈找最小值” 的 O (n) 瓶颈，需通过特殊设计记录最小值。

解题思路

  1. 这种实现的关键在于每个栈元素都包含两个信息：
    • 第一个值：当前压入栈的元素值
    • 第二个值：从栈底到当前元素的所有元素中的最小值
    • 通过这种设计，栈顶元素的第二个值始终是整个栈的最小值，从而实现了 getMin() 操作的 O (1) 时间复杂度。
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
class MinStack {
public:
    stack<pair<int,int>> stk;
    int min_val = INT_MAX;
    MinStack() {
        stk.emplace(0, INT_MAX);
    }
    
    void push(int val) {
        stk.emplace(val, min(getMin(), val));
    }
    
    void pop() {
        stk.pop();
    }
    
    int top() {
        return stk.top().first;
    }
    
    int getMin() {
        return stk.top().second;
    }
};