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

这题要求各个操作的时间复杂度都要是常数，那就意味着min这个求最小值过程不能用遍历。（不过看题目中给的数据范围，遍历应该也过得了。）那就只能采用以空间换时间的策略了，设置一个整数数组，第i个位置记录从栈底到第i个栈位置的区间的最小值（从0开始），push和pop操作都更新以栈顶位置为区间边界的区间最小值（这里偷懒并没有在pop操作里也更新）。这就是一个最简单的动态规划。其优势就是能立刻返回栈中元素的最小值，劣势也是显而易见的，即更大的空间开销。

class Solution {
  public:
    ListNode* stack;
    int min_val = (1 << 31) - 1;
    int rec_min[300]; //动态规划记录区间最小值
    int len = 0;
    void push(int value) {
        if (!stack) {
            stack = new ListNode(value);
        } else {
            ListNode* tmp = new ListNode(value);
            tmp->next = stack;
            stack = tmp;
        }
        if (!len) {
            rec_min[0] = (stack->val < min_val) ? stack->val : min_val;
        } else {
            rec_min[len] = (stack->val < rec_min[len - 1]) ? stack->val : rec_min[len - 1];
        }
        len++;

    }
    void pop() {
        if (len) {
            ListNode* tmp = stack->next;
            delete stack;
            stack = tmp;
            len--;
        }
    }
    int top() {
        if (len) {
            return stack->val;
        }
        return NULL;
    }
    int min() {
        return rec_min[len - 1];
    }
};