【题解】剑指Offer-30 包含min函数的栈

发表于 分类于 ， ， 本文字数： 186 阅读时长 ≈ 1 分钟
剑指Offer-30 包含min函数的栈 类型 水题

包含min函数的栈(剑指Offer-30)

题面

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例

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

限制

1
各函数的调用总次数不超过 20000 次

思路

除了常规的栈，再维护一个单调栈，从栈顶到栈底递增

常规栈常规添加删除元素

单调栈栈顶元素大于等于待加入元素或者单调栈为空，则入栈；当常规栈的出栈元素等于单调栈的栈顶元素，单调栈出栈

代码

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
class MinStack {
    stack<int> s, t;
public:
    /** initialize your data structure here. */
    MinStack() {

    }

    void push(int x) {
        if(t.empty() || t.top() >= x)
            t.push(x);
        s.push(x);
    }

    void pop() {
        if(t.top() == s.top())
            t.pop();
        s.pop();
    }

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

    int min() {
        return t.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->min();
 */