(LeetCode OJ) Min Stack【155】

(LeetCode OJ) Min Stack【155】

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.

Subscribe to see which companies asked this question
Hide Tags
 Stack Design
Hide Similar Problems
 (H) Sliding Window Maximum

以下是錯誤答案，有待以後調試，不捨得放棄，留了下來：

    //思路首先：數組模擬棧，入棧時直接統計最小值並放入數組  
    class MinStack {  
    public:  
        MinStack()  
        {  
            arr.resize(100000);//多麼痛的領悟  
            minarr.resize(100000);  
            ntop=-1;  
        }  
      
        void push(int x) {  
            ++ntop;  
            arr[ntop]=x;  
            if(ntop==0)  
                minum=INT_MAX;  
            if(x<=minum)  
                minum=x;  
            minarr[ntop]=minum;  
        }  
      
        void pop() {  
            minarr[ntop]=0;  
            ntop--;  
        }  
      
        int top() {  
            return arr[ntop];  
        }  
      
        int getMin() {  
            return minarr[ntop];  
        }  
    private:  
        vector<int> arr;  
        vector<int> minarr;  
        int ntop;  
        int minum;  
    };  

 

    //思路首先：數組模擬棧  
    //在壓棧的時候，直接統計出當前最小值minum放入數組  
    //出棧時，更新當前最小值minum（第一次忘了）~  
    class MinStack {  
    public:  
        MinStack()  
        {  
            arr.resize(100000);//多麼痛的領悟  
            minarr.resize(100000);  
            ntop=-1;  
        }  
      
        void push(int x) {  
            arr[++ntop]=x;  
            if(ntop==0)  
                minum=INT_MAX;  
            if(x<=minum)  
                minum=x;  
            minarr[ntop]=minum;  
        }  
      
        void pop() {  
            minarr[ntop]=0;  
            ntop--;  
            minum=minarr[ntop];//上面的代碼缺少這一行  
        }  
      
        int top() {  
            return arr[ntop];  
        }  
      
        int getMin() {  
            return minarr[ntop];  
        }  
    private:  
        vector<int> arr;  
        vector<int> minarr;  
        int ntop;  
        int minum;  
    };  

學習別人家的算法設計：他這樣處理其實還是在壓棧時就獲取了最小值。

相較普通的棧，題目要求多實現一個操作getMin(): 獲取棧中最小的元素   

我們維護兩個棧：普通棧s保存所有元素, 最小棧mins保存s中的“曾出現過”的最小元素的遞減序列。

mins.top()即為getMin()的返回值，標識普通棧s裡的最小元素。


考慮壓棧 3 4 5 2 3 1, 它們有如下表現：

push   3 4 5 2 3 1

s         3 4 5 2 3 1

mins   3       2    1

亦即，當push(x)的x < mins.top()時，我們將x壓入mins中。

大家可以發現，在上述push操作的任意間隔加我們若調用getMin()函數，mins.top()即為所求。


接下來考慮pop()操作，當且僅當s.top() == mins.top()時，我們才彈出mins的元素，這樣就可以維護mins.top()始終為當前s裡的最小值的性質。

 

    class MinStack     
    {    
    public:    
        void push(int x)     
        {    
            s.push(x);            
            if (mins.empty() || x <= mins.top() )    
                mins.push(x);                              
        }    
        
        void pop()     
        {    
            if (mins.top() == s.top())    
            {    
                s.pop();    
                mins.pop();    
            } else  {    
                s.pop();    
            }    
        }    
        
        int top()     
        {    
            return s.top();    
        }    
        
        int getMin()     
        {    
            return mins.top();    
        }    
        
    private:    
        stack<int> s;    
        stack<int> mins;    
    };