Description

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.

Example:

1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

 

Solution

用一个普通的栈完成栈的一般功能。另外用一个栈维护一个递减数列。

递减栈的目的是保证该栈的栈顶即是普通栈中所有数的最小值。因此递减栈维护的规则是：

1.普通栈push时若递减栈为空，进栈。（体现为只有一个数时该数即是最小值）

2.普通栈push时若新的数元素小于等于递减栈的栈顶，进栈。（体现为有更小的值加入）

3.普通栈pop时如果出栈的数与递减栈的栈顶相等，递减栈也出栈一个数。（体现为最小的数已经出栈，递减栈的栈顶变成了次小值）

 

Code

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
class MinStack
{
public:
    stack<int> S;
    stack<int> s_min;
    MinStack() {}
    void push(int x)
    {
        S.push(x);
        if(s_min.empty() || x <= getMin())
        {
            s_min.push(x);
        }
    }
    void pop()
    {
        if(S.top() == getMin())
        {
            s_min.pop();
        }
        S.pop();
    }
    int top()
    {
        return S.top();
    }
    int getMin()
    {
        return s_min.top();
    }
};