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(); */新聞熱點
疑難解答
