实现一个带有min()函数的栈，在 O(1) 时间内取得最小元素

要求：

实现一个带有min()函数的栈，在 O(1) 时间内取得最小元素

做法：

1. 定义两个栈，其中一个栈MinStack用于存储各个阶段的最小值；
2. 当元素入栈时，对于普通栈只是正常压入，对于MinStack则先取得MinStack的栈顶元素与压栈元素比较，压入他们之中的较小者；
3. 弹栈时，两个栈都弹栈；

代码如下：

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

#include <iostream>
#include <stack>
using namespace std;
class MinStack {
    stack<int> s;
    stack<int> minStack;
public:
    void push(int x) {
        if (s.empty()) {
            s.push(x);
            minStack.push(x);
        }else{
            s.push(x);
            int k = minStack.top();
            if (k<=x) {
                minStack.push(k);
            }else{
                minStack.push(x);
            }
        }
    }

    void pop() {
        s.pop();
        minStack.pop();
    }

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

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

Comments