?LeetCode刷題實戰(zhàn)155：最小棧
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.
題意
push(x) —— 將元素 x 推入棧中。
pop() —— 刪除棧頂?shù)脑亍?/span>
top() —— 獲取棧頂元素。
getMin() —— 檢索棧中的最小元素。
輸入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
輸出：
[null,null,null,null,-3,null,0,-2]
解釋：
MinStack minStack = new?MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
解題
public?class?MinStack?{
????private?LinkedListstack;
????Listarray;
????int?min;
????public?MinStack()?{
????????stack?= new?LinkedList<>();
????????array?= new?ArrayList<>();
????????min = Integer.MAX_VALUE;
????}
????public?void?push(int?x)?{
????????stack.push(x);
????????array.add(x);
????????min = Math.min(min, x);
????}
????public?void?pop()?{
????????int?num = stack.pop();
????????array.remove(array.size() - 1);
????????if(array.size() > 0) {
????????????min = array.get(0);
????????????for?(int?i = 0; i < array.size(); i++) {
????????????????if(min > array.get(i)) {
????????????????????min = array.get(i);
????????????????}
????????????}
????????}else?{
????????????min = Integer.MAX_VALUE;
????????}
????}
????public?int?top()?{
????????return?stack.peek();
????}
????public?int?getMin()?{
????????return?min;
????}
}