LeetCode OJ：Min Stack（最小栈问题）

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.

设计一个最小栈，使得返回栈中的最小数的这个操作的时间复杂度为常数，用双栈实现，一个栈作为最小数的保存栈，代码如下：

 class MinStack {

 public:

     void push(int x)

     {

         s.push(x);

         if(sMin.empty() || x <= sMin.top())

             sMin.push(x);

     }

     void pop()

     {

         if(s.top() == sMin.top()){

             sMin.pop();

         }

         s.pop();

     }

     int top()

     {

         return s.top();

     }

     int getMin()

     {

         return sMin.top();

     }

 private:

     stack<int> s;

     stack<int> sMin;

 };

巴特西

LeetCode OJ：Min Stack（最小栈问题）

最新文章

热门文章