剑指30题解 | #包含min函数的栈#

/*
    重点理解时间复杂度O(1)
    min也得一次，那么可以尝试使用另外一个栈的top存着当前序列最小值即可，注意与现有栈容量对齐并动态更新
*/
#include <algorithm>
#include <stack>
class Solution {
public:
    stack<int> d1, d2;  // 目的保证操作时间复杂度为1
    void push(int value) {
        d1.push(value);
        // if(d2.empty())   // 容器d2为空时，直接加入元素
        // {
        //     d2.push(value);
        // }
        // if (d2.top() > value) {  // 后来元素更小，则入栈，更新最小为top
        //     d2.push(value); 
        if(d2.empty() || d2.top() > value){
            d2.push(value);
        }else{
            d2.push(d2.top());  // 若后来元素较大，则入栈本来top值；目的保证d1栈中的同等高度的top，在d2都是最小的
        }
    }
    void pop() {
        d1.pop();
        d2.pop();   // 对齐d1操作
    }
    int top() {
        return d1.top();
    }
    int min() {
        return d2.top();    // d2的top都是记录容器当前top高度的最小值
    }
};