剑指offer - 包含min函数的栈

发表于 | 更新于

题目

https://www.nowcoder.com/questionTerminal/4c776177d2c04c2494f2555c9fcc1e49

题意

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

题解

定义两个栈，一个栈（value）正常用，另一个栈（min）存放栈底到栈顶的最小元素，push时，比较min栈栈顶元素的push元素的值，压入两者中较小值。pop时，min栈也弹出。所以min栈顶即为当前栈中所有元素的最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
private:
    stack<int> valueStack;
    stack<int> minStack;
public:
    void push(int value) {
        valueStack.push(value);
        if(minStack.empty()||value<minStack.top())
            minStack.push(value);
        else
            minStack.push(minStack.top());
    }
    void pop() {
        valueStack.pop();
        minStack.pop();
    }
    int top() {
        return valueStack.top();
    }
    int min() {
        return minStack.top();
    }
};