題目描述

xxxx簡單來說，設計一個堆疊，除了基本的push、pop、top操作，還需要設計一個直接可以獲取堆疊中元素最小值的介面，

思路一（錯誤的）

xxxx我估計大多數人都會像我一樣，犧牲堆疊中第一個位置，或者創建一個成員變數，用來存盤最小值，當push資料的時候就與這個最小值進行比較，如果push的新資料小于最小值，那么就更新最小值，
xxxx但是這種想法是錯誤的，舉一個例子來印證這個錯誤，
錯誤原因：假如堆疊中的資料是{ 2,1,0 }，那么此時最小值 min=0，當我們pop掉堆疊頂資料0時，min就要被更新，而更新的話，就要遍歷整個堆疊中資料，而堆疊中的資料又無法直接遍歷，所以這種想法是錯誤的，

思路二（時間復雜度O（1）、空間O（N））

初版思想

xxxx有一個很好的思路，就是額外使用一個輔助堆疊，這個輔助堆疊就是存盤最小值，每次呼叫getMin時，直接取輔助堆疊的堆疊頂資料就是當前堆疊中資料的最小值
分析原因:其實這也依賴了堆疊的后進先出的原理，這個最后再印證，
1、首先，push第一個資料a后，堆疊中只有一個資料，當然最小的資料就是它自己，所以我們在輔助堆疊中push該資料a，表明堆疊中該位置及以前所有資料中a是最小的，
2、然后我們再push第二個資料b，
（1）如果b>a，說明在堆疊中所有資料中a仍然是最小的，那么在輔助堆疊中仍然push進a，說明，在該位置及以前所有資料中，仍然是a最小
（2）如果b<=a，說明b是目前堆疊中所有資料中最小的數，那么就要push進b，最小值就更新成b
3、重復（2）步驟知道資料push結束，，，，
4、解釋為何依賴了堆疊的后進先出的特點：在push資料的時候，我們就可以得到插入每一個數字之后，最小值，在pop資料時，由于最先pop出堆疊的是最新更新的最小值，資料pop，最新更新的最小值也隨之出堆疊，這樣剩下的內容就相當于從來沒有push過該資料，剩下的堆疊依然符合既定的結構，
如果不是堆疊，是佇列的話就無法成功，因為pop出的是最先插入的最小值，具體大家可以自己舉個例子試驗一下，很容易驗證！
舉一個例子具體闡明：

決議
xxxx1、先在堆疊中push進2，那么堆疊中只有2這個數字，所以最小值就是2，所以在下面輔助堆疊中push進2.
xxxx2、再在堆疊中push進5，5與輔助堆疊堆疊頂資料（原先堆疊中最小資料）2比較，5大，所以最小值不變，那么我們繼續在輔助堆疊中push進2，
xxxx3、再push進1,1與輔助堆疊堆疊頂資料（原先堆疊中最小資料）2比較，1小，那么最小值就更新成1，在輔助堆疊中push進1，
xxxx4、再在堆疊中push進0,0與輔助堆疊堆疊頂資料（原先堆疊中最小資料）1比較，0小，那么最小值就更新成0，在輔助堆疊中就push進0，

代碼實作：

class MinStack {
public:
    /** initialize your data structure here. */
    //建構式，可以不寫
    MinStack() {

    }
    
    void push(int val) {
        st.push(val);
        if(help.empty())
        {
            help.push(val);
        }
        else
        {
            //如果新插入資料大于原先輔助堆疊堆疊頂資料（原最小資料），那么最小資料不變，還是堆疊頂資料
            if(val>help.top())
                help.push(help.top());
            //如果小于等于，那么更新最小資料
            else
                help.push(val);
        }
    }
    
    void pop() {
        st.pop();
        help.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return help.top();
    }
    //存盤資料的堆疊
    stack<int> st;
    //輔助堆疊
    stack<int> help;
};

進階思想

xxxx按照之前的想法，是可以完成的，但是會出現一個問題，那就是如果有大量連續重復的資料，就會導致空間的浪費，
例如：

xxxx這個時候我們就想到，如果出現重復的，我們就可以不去push，只寫一個，但是就會出現一個問題，例如上面最后push的兩個0.下面的輔助堆疊中只寫入一個0，這樣當我們pop一個0后，輔助堆疊也pop一個0.這樣導致的結構就是，輔助堆疊的堆疊頂元素是1了，但是堆疊中明明還有更小的0，這就出現了一個問題，因此，為了完成這個任務，我們需要記錄，在輔助堆疊中連續出現了幾次相同最小值，

3次5、4次2、3次1、2次0

代碼實作：

//創建一個結構體
struct ValueMin
{
	//最小值
    int min;
    //出現次數
    int count;
};

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {

    }
    
    void push(int val) {
        st.push(val);
        if(help.empty() || val<help.top().min)
        {
            ValueMin tmp = {val,1};
            help.push(tmp);
        }
        else
        {
            help.top().count += 1;
        }
    }
    
    void pop() {
        int value = st.top();
        st.pop();
        if(!--help.top().count)
            help.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return help.top().min;
    }

private:
	//存盤資料
    stack<int> st;
    //輔助堆疊中存盤對應最小值及出現次數 
    stack<ValueMin> help; 
};

思路二（最優解：時間復雜度O（1）、空間O（1））

演算法思想

xxxx這種方法的話，我們的 stack 堆疊中，不能存放原始數值，而是應該存放差值，啥是差值？就是存放將要push的資料與最小值的差值，我還是詳細一點給大家講一個案例吧，案例配合代碼，應該還是挺好理解的，例如 arr = {3, 2, 2, 4, 0}，那么把這些元素入堆疊時，stack 堆疊中元素以及最小值的變化如下：
差值 = 將要入堆疊元素數值 - 當前最小值

代碼實作：

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {

    }
    
    void push(int val) {
        if(st.empty())
        {
            //第一個資料，默認為0
            st.push(0);
            min = val;
        }
        else
        {
            long gap = val - min;
            st.push(gap);
            min = gap<0 ? val : min;
        }
    }
    
    void pop() {
        long top = st.top();
        //top<=0,說明要pop掉的資料就是最小值，所以要pop后要更新最小值
        if(top<=0)
        {
            //top = 最后插入的資料-之前的最小值，所以之前的最小值 = 最后插入的資料-top
            //因為top<=0,所以最后插入的值，就是現在最小值
            min = min - top;
        }
        st.pop();
       /* else
        {
            //top大于0，所以產出堆疊頂元素，最小值不變
            //其實else不需要，我是為了讀者理解才寫出
            min = min;
        }
        */
    }
    
    int top() {
        long top = st.top();
        if(st.top()<=0)
            return min;
        else
            return (int)(min+top);
        //top = 最后插入的資料-之前的最小值，所以 最后插入的資料=top+之前的最小值
        //因為top>0,所以之前的最小值和當前的最小值相同
            
    }
    
    int getMin() {
        return (int)min;
    }
    stack<long> st;
    long min;
};

注：這里有一個關鍵的問題，就是，當我們堆疊st和min都使用int型別時，會有一個整形溢位的bug，如圖

為什么會出現這種情況？原因是如下代碼

如果gap是int型別，那么gap = val - min時，有情況會使gap整形溢位，
1、val為整形最大值，min為負數時，兩者相減，就會使gap溢位
2、val為整形最小值，min為正數時，兩者相減，也會使gap溢位
所以，我們先全部用long型別變數存資料，回傳時再強轉成int型別，

總結

xxxx我們梳理一下最小堆疊的需要的功能，1、需要像普通堆疊一樣存盤、讀取資料，2、需要以時間復雜度為O(1)的代價獲取最小值，而存差值的方法是如何完成兩項任務的呢？首先獲取最小值很簡單，直接使用min變數來獲取，問題就是堆疊中存的是差值，如何轉換成原數值呢？
xxxx答案就是，當存盤的差值<=0時，說明將要push進來的值小于等于原先的最小值，最小值就需要更新，因此此時的min就等于該數值，
xxxx當存盤的差值>0時，就說明，將要push進來的值是大于原先的最小值的，min還等于原來的值，差值 = 數值 - min，所以數值 = 差值+min，這樣就得到了原數值，

綜上

xxxx這道題想要過的話，加以思考還是不算難的，如果要求效率極致，就要相處更優秀的演算法（思路二）我認為還是比較困難，大家只有多看多練多思考，將知識融會貫通才有可能成為“演算法大師”，
xxxx如果大家看完這篇文章有什么感想或者有其他解題思想都可以發表在評論區，或者直接私信我，我們共同學習，共同進步！