剑指 Offer 30 包含min函数的栈

概述

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

https://leetcode.com/problems/min-stack/

双栈法

题目就算让我们在标准的栈上使其支持 O(1) 的最小值查询。

我们采用双栈，一个栈用于记录压入的数据，另一个用于记录当前最小值。

class MinStack {
public:
    stack<int> a;
    stack<int> b;
    MinStack() {
        
    }
    
    void push(int val) {
        a.push(val);
        if (b.empty() || val < b.top()) {
            b.push(val);
        } else {
            b.push(b.top());
        }
    }
    
    void pop() {
        a.pop();
        b.pop();
    }
    
    int top() {
        return a.top();
    }
    
    int getMin() {
        return b.top();
    }
};