本文共 1399 字，大约阅读时间需要 4 分钟。

155. 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.

Example 1:

Input["MinStack","push","push","push","getMin","pop","top","getMin"][[],[-2],[0],[-3],[],[],[],[]]Output[null,null,null,null,-3,null,0,-2]ExplanationMinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin(); // return -3minStack.pop();minStack.top();    // return 0minStack.getMin(); // return -2

Constraints:

Solution

Runtime: 48 ms, faster than 23.55% of C++ online submissions for Min Stack.

class MinStack {   private:    stack
   
     s1, s2;public:    /** initialize your data structure here. */    MinStack() {               }        void push(int x) {           if(s2.empty() || x <= getMin()) s2.push(x);        s1.push(x);    }        void pop() {           if(s1.top()==getMin()) s2.pop();        s1.pop();    }        int top() {           return s1.top();    }        int getMin() {           return s2.top();    }};
   

使用双栈，一个存放当前最小元素，另一个存放所有元素。