155. Min Stack

• 题目：
  题目地址

• 题目描述
  请设计一个栈结构，支持 push、pop、top以及getMin操作，且每个操作的时间复杂度都是 O(1)O(1)。

  push(x) – 向栈中压入元素 xx；
  pop() – 删除栈顶元素；
  top() – 返回栈顶元素；
  getMin() – 返回栈中的最小元素；

• 题解：
  我们除了维护基本的栈结构之外，还需要维护一个单调栈，来实现返回最小值的操作。
  下面介绍如何维护单调栈：

  1. 当我们向栈中压入一个数时，如果该数 ≤≤ 单调栈的栈顶元素，则将该数同时压入单调栈中；
     否则，不压入，这是由于栈具有先进后出性质，所以在该数被弹出之前，栈中一直存在一个数比该数小，所以该数一定不会被当做最小数输出。

  2. 当我们从栈中弹出一个数时，如果该数等于单调栈的栈顶元素，则同时将单调栈的栈顶元素弹出。

  3. 单调栈的栈顶元素，就是当前栈中的最小数。！

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); //如果单调栈为空，或者当前要压入的元素比单调栈中的元素还小，则将该元素也压入单调栈。
        }
    }
    
    void pop() {
        if (stackMin.top()==stackValue.top() ){//当单调栈中的元素和栈中要pop的元素相等时，也把单调栈中的该元素也pop
            stackMin.pop();
        }
        stackValue.pop();

    }

    
    int top() {
        return stackValue.top();
    }
    
    int getMin() {
        return stackMin.top();//单调栈中的栈顶元素一直是最小值
    }
};

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