题解 | #包含min函数的栈#

#include <vector>
/*
 *思路是设计以pair{value,min_ptr}为元素的栈,
 *每次插入,需额外比较旧栈顶最小值的记录以保持栈顶最小值有效
*/
class Solution {
  private:
    vector<pair<int, int>>kcats;//stack二元栈,附加当前栈深最小值指针
    int cur;//栈顶指针,0开始
  public:
    Solution() {
        //初始化栈,立哨兵,内置逻辑最大值
        kcats.emplace_back(0x0fffffff, 0);
        cur = 0;
    }
    void push(int value) {
        //获取最小值指针,cur++
        int min_loc = kcats[cur++].second;

        //动态扩容避免溢出
        if (kcats.capacity() <= cur)
            kcats.resize(cur << 1);

        //value入栈,比较最小值,若前最小值更小则记录其指针,否则更新为cur
        kcats[cur] = {value, ((value <= kcats[min_loc].first) ? cur : min_loc)};
    }
    void pop() {
        //懒处理
        if (cur > 0)cur--;
    }
    int top() {
        return kcats[cur].first;
    }
    int min() {
        return kcats[kcats[cur].second].first;
    }
};