题解 | 包含min函数的栈

#include <stack>
#include <algorithm>
using namespace std;

class Solution {
  private:
    stack<int> dataStack;    // 主数据栈
    stack<int> minStack;     // 最小栈，栈顶始终是当前最小值

  public:
    void push(int value) {
        // 压入主栈
        dataStack.push(value);

        // 如果最小栈为空，或者当前值 <= 最小栈栈顶，则压入最小栈
        if (minStack.empty() || value <= minStack.top()) {
            minStack.push(value);
        }
    }

    void pop() {
        // 如果弹出的元素等于最小栈栈顶，则最小栈也要弹出
        if (dataStack.top() == minStack.top()) {
            minStack.pop();
        }
        dataStack.pop();
    }

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

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

核心思想
使用两个栈：
stack：正常存储所有元素
min_stack：存储当前主栈中的最小值序列

关键操作说明
push操作：
总是将元素压入主栈
只有当最小栈为空，或者当前值 ≤ 最小栈栈顶时，才压入最小栈
这样保证最小栈栈顶始终是当前主栈中的最小值

pop操作：
从主栈弹出元素
如果弹出的元素等于最小栈栈顶，说明当前最小值要被移除，所以最小栈也要弹出
这样保证最小栈栈顶始终反映当前主栈的最小值