剑指offer30 包含min函数的栈

发表于 | 分类于 |
字数统计: 240 | 阅读时长 ≈ 1

链接: https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/

题意

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

解法

设定一个辅助栈 存非严格递减的栈
每次调用min的时候传辅助栈的栈顶
调用pop的时候 如果辅助栈顶也是一样的值就进行pop
调用push的时候 判断是否和小于等于辅助栈栈顶
等于是为了防止当存在两个相同的最小值被pop掉

代码

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
class MinStack {
public:
    /** initialize your data structure here. */
    vector<int> stk1;
    vector<int> stk2;
    MinStack() {
    }
    
    void push(int x) {
        stk1.push_back(x);
        if (stk2.empty() || stk2.back() >= x) {
            stk2.push_back(x);
        }
    }
    
    void pop() {
        if (stk2.size() && stk2.back() == stk1.back()) {
            stk2.pop_back();
        }
        stk1.pop_back();
    }
    
    int top() {
        return stk1.back();
    }
    
    int min() {
        return stk2.back();
    }
};