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.
Example:
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2.
This problem looks simple, but pay attention to what happens when popping from the stack if the minimum value is popped. How do you solve this?
class MinStack { Stack s = new Stack(); Stack ms = new Stack(); int min = Integer.MAX_VALUE; /** initialize your data structure here. */ public MinStack() { } public void push(int x) { s.push(x); if(min>x){ min = x; } ms.push(min); } public void pop() { s.pop(); ms.pop(); if(s.isEmpty()){ min = Integer.MAX_VALUE; } else{ min = ms.peek(); } } public int top() { return s.peek(); } public int getMin() { return min; } } /** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(x); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */ This siteOriginal articleAll follow "Attribution-NonCommercial-ShareAlike 4.0 License (CC BY-NC-SA 4.0)Please retain the following annotations when sharing or adapting:
Original author:Jake Tao,source:"155. Min Stack"
