DAY 24
0

## 【從面試題學邏輯-24】 如何製作能馬上找到最小值的stack？（leetcode 155. Min Stack）

(這題和CTCT 3.2一樣喔)

，就是必須這樣做才行。如果不能夠loop，就必須額外開空間來存，而且存數字進去的當下，就必須要記錄當下的最小值

``````class MinStack {
Stack<Integer> s;
Stack<Integer> mins;

/** initialize your data structure here. */
public MinStack() {
s = new Stack<Integer>();
mins = new Stack<Integer>();
}

public void push(int x) {
if(s.isEmpty() || x <= mins.peek()){
mins.push(x);
}else{
mins.push(mins.peek());
}
s.push(x);
}

public void pop() {
s.pop();
mins.pop();
}

public int top() {
return s.peek();
}

public int getMin() {
return mins.peek();
}
}
``````

``````Stack<Integer> s;
Stack<Integer> mins;

/** initialize your data structure here. */
public MinStack() {
s = new Stack<Integer>();
mins = new Stack<Integer>();
}
``````

``````public void push(int x) {
if(s.isEmpty() || x <= mins.peek()){
mins.push(x);
}else{
mins.push(mins.peek());
}
s.push(x);
}
``````

（stack代表正常存值的那條，minStack就是專門記最小值的那條）

``````public void pop() {
s.pop();
mins.pop();
}
``````

``````public int top() {
return s.peek();
}

public int getMin() {
return mins.peek();
}
``````

`top()``getMin()`就理所當然的用`peek()`偷看一下`s`/`mins`最外面的東西