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.

---

思路：须要两个栈，一个用来作为一般的栈，还有一个用来存放进栈到某一位置的当前站内最小元素。代码例如以下：

Code（c++）:

class MinStack {public:    std::stack
      
        stk;    std::stack
       
         min;    void push(int x) {        stk.push(x);        if(min.empty() || (!min.empty() && x <= min.top())){            min.push(x);        }    }    void pop() {        if(!stk.empty()){            if(stk.top() == min.top())min.pop();            stk.pop();        }    }    int top() {        if(!stk.empty())            return stk.top();    }    int getMin() {        if(!stk.empty()) return min.top();    }};
       
      

版权声明：本文博主原创文章，转载请注明出处。