---
# System prepended metadata

title: 0155. Min Stack
tags: [Leetcode, Medium, Stack]

---

# 0155. Min Stack
###### tags: `Leetcode` `Medium` `Stack`
Link: https://leetcode.com/problems/min-stack/
## 思路 $O(1) for \ each \ operation$ $O(N)$
双栈，一个记录所有的数字，一个记录所有出现过的最小值（和find next smaller 不一样）
例如 $num = [3,5,2,4,1]$, 那么$min = [3,2,1]$
pop的时候，首先pop掉1，因为min.peek()=1，那么min也要被pop，这样$num = [3,5,2,4]$ $min = [3,2]$，min.peek()永远是num里面现存数字的最小值
## Code
```java=
class MinStack {
    Stack<Integer> num;
    Stack<Integer> min;
    
    public MinStack() {
        num = new Stack<>();
        min = new Stack<>();
    }
    
    public void push(int val) {
        num.add(val);
        if(min.isEmpty() || val<=min.peek()){
            min.add(val);
        }
    }
    
    public void pop() {
        int popNum = num.pop();
        if(!min.isEmpty() && popNum == min.peek()){
            min.pop();
        }
    }
    
    public int top() {
        return num.peek();
    }
    
    public int getMin() {
        return min.peek();
    }
}
```