题目

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

  • push(x) —— 将元素 x 推入栈中。
  • pop() —— 删除栈顶的元素。
  • top() —— 获取栈顶元素。
  • getMin() —— 检索栈中的最小元素。

示例:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

  • pop、top 和 getMin 操作总是在 非空栈 上调用。

题解

这道题之前有做过，但这次再做时，只是依稀记得可能需要另外一个栈，但具体要怎么搞还是忘记了。既然这样，做题的意义何在呢？

直接的思路还是维护一个队列，按照从小到大的顺序排列当前栈中的值，若要获取最小值时，直接读取队列的首元素就行。对应的实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

class MinStack {
public:
   /** initialize your data structure here. */
   MinStack() {

   }

   void push(int x) {
       s.push(x);
       
       bool inserted = false;
       for (auto itr = l.begin(); itr != l.end(); itr++) {
           if(x < *itr){
               l.insert(itr, x);
               inserted = true;
               break;
           }
       }

       if (!inserted) {
           l.push_back(x);
       }
   }

   void pop() {
       int value = s.top();
       for (auto itr = l.begin(); itr != l.end(); itr++) {
           if (*itr == value) {
               l.erase(itr);
               break;
           }
       }

       s.pop();
   }

   int top() {
       return s.top();
   }

   int getMin() {
       return *l.begin();
   }

private:
   stack<int> s;
   list<int> l;
};

这里的队列没有使用标准库中的队列，而是用list模拟了一个队列，在插入元素时，将元素插入到list中，而在pop时，也需要将pop出的元素从list中移除。整体来说，push和pop的复杂度是O(N)，而getMin的复杂度是O(1)，满足要求，在提交代码后也可测试通过。

最后还是查看了讨论，常用的思路是使用辅助栈。使用辅助栈的实现中，push和pop的时间复杂度均为O(1)，对应的实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
    }

    void push(int x) {
        s.push(x);
        if (l.empty())
            l.push(x);
        else {
            if (x <= l.top())
                l.push(x);
        }
    }

    void pop() {
        if (s.top() == l.top())
            l.pop();

        s.pop();
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return l.top();
    }

private:
    stack<int> s;
    stack<int> l;
};

// 或是下面这种实现
class MinStack {
    stack<int> x_stack;
    stack<int> min_stack;
public:
    MinStack() {
        min_stack.push(INT_MAX);
    }
    
    void push(int x) {
        x_stack.push(x);
        min_stack.push(min(min_stack.top(), x));
    }
    
    void pop() {
        x_stack.pop();
        min_stack.pop();
    }
    
    int top() {
        return x_stack.top();
    }
    
    int getMin() {
        return min_stack.top();
    }
};

上面两种实现中都是使用的辅助栈，但在细节上略有些不同，下面那种实现可能会更为广泛，简单来说就是每push一个元素，都把当前栈中的最小元素push到辅助栈中，当pop时一并pop出辅助栈的元素，辅助栈的栈顶一直存储当前栈的最小值。

而在上面那种实现中，理解起来会稍微有些困难，它并不是每当push就push最小值，而是只有当push的元素小于当前的最小元素时才进行push，在pop时也同样，只有当pop的元素与辅助栈的栈顶一致时才pop出。

两种实现中，下面那种会更加人理解和记忆。总的来说，我们需要一个结构实时的存储当前栈的最小元素，并随着栈的push和pop不断的更新当前栈的最小元素。