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.s思路： 1. 关键就是最小值的计算。每次进来一个数，计算出最小值，然后把这个最小值当个小尾巴和这个数放一起就可以了。比如，存成pair。也就是，相当于做了distributed的操作，让每个数进来的时候，就告诉这个数，现在谁是最小值，等有人问现在最小值是多少，站在stack顶上的哥们就掏出自己知道的最小值回答他！ 2.调试的时候，容易忽略一点：往stack push数据时，容易想到计算当前最小值，但往外pop数据时，却忽略了也要重新update最小值。即使这也想到了，却容易忽略一个极端情况：当stack被pop空了后，当前最小值需要回到初始化的值INT_MAX。 3. 通过一番琢磨自己的思路，发现思路的问题：1. 不注重对称性，本来更新最小值是在操作的全过程都需要的，包括push和pop，这是最大的事实，而头脑里面的思维和这个事实还没有明显的对接，只是明显知道需要在push时计算，没有意识在pop的时候也需要计算，而push和pop是对称的操作。以后对这种对称的操作，都应该同时平等的考虑，没有谁重要或不重要，我想这应该是潜意识里给push进来这个操作赋予了更高优先级和更重要位置，从而pop这个操作就给选择性遗忘。因此，需要打破这种人为的贴标签的态度，认为某个操作重要，作为一个完整的系统，任何一部分都同等重要，或都不重要！ 4. 还有一点是：对极限的考虑。极限情况，就是当stack空的时候，是否stack里面所有的状态都恢复到初始状态。这就需要有极限的思维，站在极端的情况下看问题，看到的世界就不同。但首先需要有意识的站在极端的世界里去，就自然可以看到解决的方法！立场决定了视野！
class MinStack {PRivate: int curmn; vector<pair<int,int>> res;public: /** initialize your data structure here. */ MinStack() { curmn=INT_MAX; } void push(int x) { curmn=min(x,curmn); res.push_back({x,curmn}); } void pop() { if(res.empty()) return; res.pop_back(); curmn=res.empty()?INT_MAX:getMin();//bug: } int top() { return res.back().first; } int getMin() { return res.back().second; }};/** * 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(); */新闻热点
疑难解答
