题目描述
设计一个支持push，pop，top等操作并且可以在O(1)时间内检索出最小元素的堆栈。
- push(x)–将元素x插入栈中
- pop()–移除栈顶元素
- top()–得到栈顶元素
- getMin()–得到栈中最小元素
数据范围
操作命令总数 [0,100]。
样例
MinStack minStack = new MinStack(); minStack.push(-1); minStack.push(3); minStack.push(-4); minStack.getMin(); --> Returns -4. minStack.pop(); minStack.top(); --> Returns 3. minStack.getMin(); --> Returns -1.
方法一：单调栈 O(1)
这道题我们除了要维护一个普通的堆栈之外， 还要维护一个单调栈：
在 push 元素时，要判断该元素是否小于等于单调栈的栈顶，如果小于就 push 进去；否则，就只 push 到普通栈中。这里不放入单调栈是因为栈的先进后出的性质，单调栈中一定存在一个比该数要小并且在它后面弹出的元素。
弹出元素时，如果普通栈栈顶和单调栈栈顶元素相同，则两个栈都要 pop 出来。
单调栈栈顶的元素就是我们要找的最小元素。
我们拿题目样例来举例，看看具体的实现过程：
第一步：push(-1) ，此时单调栈为空，直接放进去即可。
第二步：push(3) ，要大于单调栈栈顶，故只推入正常栈中。
第三步：push(-4) ，比单调栈栈顶小，故要推入单调栈中。
第四步：getMin() ，返回单调栈栈顶元素 -4 。
第五步：pop() ，弹出的栈元素等于单调栈栈顶元素，故单调栈栈顶也需弹出。
第六步：top() ，返回正常栈栈顶元素 3 。
第七步：getMin() ，返回单调栈栈顶元素 -1 。
class MinStack { public: /** initialize your data structure here. */ stack<int> stackValue; stack<int> stackMin; MinStack() { } void push(int x) { stackValue.push(x); if (stackMin.empty() || stackMin.top() >= x) stackMin.push(x); } void pop() { if (stackMin.top() == stackValue.top()) stackMin.pop(); stackValue.pop(); } int top() { return stackValue.top(); } int getMin() { return stackMin.top(); } }; /** * 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(); */
欢迎大家在评论区交流~
