155. Min Stack
Easy
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack
class:
MinStack()
initializes the stack object.void push(val)
pushes the elementval
onto the stack.void pop()
removes the element on the top of the stack.int top()
gets the top element of the stack.int getMin()
retrieves the minimum element in the stack.
Example 1:
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2
Constraints:
-2^31 <= val <= 2^31 - 1
- Methods
pop
,top
andgetMin
operations will always be called on non-empty stacks. - At most
3 * 10^4
calls will be made topush
,pop
,top
, andgetMin
.
思路
用一个栈 data
存放数据,同时记录当前全局最小的元素 current_min
,同时维护一个栈 min
存放每个位置的最小元素。两个栈保持高度相同。
当新数据 push 入data
栈时,更新全局最小元素 current_min
,并将其压入 min
。
当 data
栈 pop 时,同步 pop min
,并更新 current_min
为 min
栈顶元素。若 min
为空,则将 current_min
重置为 INT_MAX
。
class MinStack {
private:
stack<int> data;
stack<int> min;
int current_min = INT_MAX;
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int val) {
data.push(val);
if (val < current_min) {
current_min = val;
}
min.push(current_min);
}
void pop() {
data.pop();
min.pop();
if (!min.empty()) current_min = min.top();
else current_min = INT_MAX;
}
int top() {
return data.top();
}
int getMin() {
return min.top();
}
};
Runtime: 16 ms, faster than 96.78% of C++ online submissions for Min Stack.
Memory Usage: 16.2 MB, less than 22.25% of C++ online submissions for Min Stack.
(考虑到 min
栈中的元素大多是连续重复值,后续可以将其改进为计数的形式进行压缩优化。)