2026/05/12

[LeetCode] 155 Min Stack

要怎麼知道stack當前元素內的「最小值」?

每次push時, 若當前element比minVal更小

則先把min給push進去, 再push當前element, 並且更新minVal

超有趣, 一次push兩個element進去!!

pop時還可以用這個多push進去的「次小值」還原成「最小值」

 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
class MinStack {
private:
  std::stack<int> _stack;
  int minVal;

public:
  MinStack() { minVal = INT_MAX; }

  void push(int x) {
    if (x <= minVal) {
      _stack.push(minVal);
      minVal = x;
    }
    _stack.push(x);
  }

  void pop() {
    int topVal = _stack.top();
    _stack.pop();
    if (topVal == minVal) {
      minVal = _stack.top();
      _stack.pop();
    }
  }

  int top() { return _stack.top(); }

  int getMin() { return minVal; }
};

/**
 * 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();
 */
Labels: