• 題目：
  題目地址

• 題目描述
  請(qǐng)?jiān)O(shè)計(jì)一個(gè)棧結(jié)構(gòu)，支持 push、pop、top以及getMin操作，且每個(gè)操作的時(shí)間復(fù)雜度都是 O(1)O(1)。

  push(x) – 向棧中壓入元素 xx；
  pop() – 刪除棧頂元素；
  top() – 返回棧頂元素；
  getMin() – 返回棧中的最小元素；

• 題解：
  我們除了維護(hù)基本的棧結(jié)構(gòu)之外，還需要維護(hù)一個(gè)單調(diào)棧，來實(shí)現(xiàn)返回最小值的操作。
  下面介紹如何維護(hù)單調(diào)棧：

  1. 當(dāng)我們向棧中壓入一個(gè)數(shù)時(shí)，如果該數(shù) ≤≤ 單調(diào)棧的棧頂元素，則將該數(shù)同時(shí)壓入單調(diào)棧中；
     否則，不壓入，這是由于棧具有先進(jìn)后出性質(zhì)，所以在該數(shù)被彈出之前，棧中一直存在一個(gè)數(shù)比該數(shù)小，所以該數(shù)一定不會(huì)被當(dāng)做最小數(shù)輸出。

  2. 當(dāng)我們從棧中彈出一個(gè)數(shù)時(shí)，如果該數(shù)等于單調(diào)棧的棧頂元素，則同時(shí)將單調(diào)棧的棧頂元素彈出。

  3. 單調(diào)棧的棧頂元素，就是當(dāng)前棧中的最小數(shù)。！

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); //如果單調(diào)棧為空，或者當(dāng)前要壓入的元素比單調(diào)棧中的元素還小，則將該元素也壓入單調(diào)棧。
        }
    }
    
    void pop() {
        if (stackMin.top()==stackValue.top() ){//當(dāng)單調(diào)棧中的元素和棧中要pop的元素相等時(shí)，也把單調(diào)棧中的該元素也pop
            stackMin.pop();
        }
        stackValue.pop();

    }

    
    int top() {
        return stackValue.top();
    }
    
    int getMin() {
        return stackMin.top();//單調(diào)棧中的棧頂元素一直是最小值
    }
};

/**
 * 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();
 */