单调栈技巧总结

单调栈实际上就是栈，只是限制要比普通的栈更严格而已了。要求是每次入栈的元素必须要有序（如果新元素入栈不符合要求，则将之前的元素出栈，直到符合要求再入栈），使之形成单调递增/单调递减的一个栈。

• 单调递增栈：只有比栈顶小的才能入栈，否则就把栈顶出栈后，再入栈。出栈时可能会有一些计算。适用于求解第一个大于该位置元素。

• 单调递减栈：与单调递增栈相反。适用于求解第一个小于该位置的元素。

• 如何判断：单调递增/递减栈是根据出栈后顺序来决定的。例如，栈内元素顺序[1, 2, 6]，出栈后顺序[6, 2, 1]，这就是单调递减栈。

• 适用场景：单调栈一般用于解决 第一个大于 xxx 或者 第一个小于 xxx 这种题目。

LeetCode2104. 子数组范围和

给你一个整数数组 nums 。nums 中，子数组的范围是子数组中最大元素和最小元素的差值。
返回 nums 中所有子数组范围的和 。
子数组是数组中一个连续非空的元素序列。

• 参考：宫水三叶题解，区间DP & 单调栈

所有子数组范围的和可以表示为。

区间DP

• 枚举all subarrs：按区间起点、区间长度两层循环枚举
• 计算单个区间的max、min值：区间[i, j]的max可以由max([i, j-1]的max, nums[i])得到。min同理。[i, j]的max / min的计算仅依赖[i, j]的max / min和nums[i]。

因此，时空复杂度分别为、。

    long long subArrayRanges(vector<int>& nums) {
        int n = nums.size();
        long long res = 0;
        for(int i = 0; i < n; i++) {
            int dp_M, dp_m;
            dp_M = dp_m = nums[i];
            // res += 0;
            for(int j = i + 1; j < n; j++) {
                dp_M = max(dp_M, nums[j]);
                dp_m = min(dp_m, nums[j]);
                res += (dp_M-dp_m);
            }
        }
        return res;
    }

单调栈

观察，nums中单个元素对结果的贡献与充当子数组最值的次数有关。结果还可以表示为
区间个数 = 备选左端点数 * 备选右端点数，问题切换为：使用「单调栈」找到某个元素作为最值的备选左右端点。

• 第个元素作为子数组最大值的次数：找到它左、右最近的不满足「小于等于 nums[i]」的位置，记其为 和 。此时左端点有个选择，右端点有个选择，子数组个数为个。
• 第个元素作为子数组最小值的次数同理。
• 单调增栈维护作为最大值的区间端点，单调减栈维护作为最小值的区间端点。从左到右、从右到左各扫一遍。
• 注意，nums存在相同元素，因此两边均取等号会导致某些区间被重复计算，可令最近右端点的部分不取等号，确保区间统计不重不漏。

    long long subArrayRanges(vector<int>& nums) {
        int n = nums.size();
        stack<int> inc_stack, dec_stack;
        vector<int> left_as_max(n), left_as_min(n);
         for(int i = 0; i < n; i++) {
            // increase
            while(!inc_stack.empty() && nums[inc_stack.top()] < nums[i]) { 
                inc_stack.pop();
            }
            left_as_max[i] = inc_stack.empty() ? -1 : inc_stack.top();
            inc_stack.push(i);
            
            // decrease
            while(!dec_stack.empty() && nums[dec_stack.top()] >= nums[i]) {
                dec_stack.pop();
            }
            left_as_min[i] = dec_stack.empty() ? -1 : dec_stack.top();
            dec_stack.push(i);
        }
        while(!inc_stack.empty()) inc_stack.pop();
        while(!dec_stack.empty()) dec_stack.pop();
        vector<int> right_as_max(n), right_as_min(n);
        for(int i = n-1; i >= 0; i--) {
            while(!inc_stack.empty() && nums[inc_stack.top()] <= nums[i]) {
                inc_stack.pop();
            }
            right_as_max[i] = inc_stack.empty() ? n : inc_stack.top();
            inc_stack.push(i);

            while(!dec_stack.empty() && nums[dec_stack.top()] > nums[i]) {
                dec_stack.pop();
            }
            right_as_min[i] = dec_stack.empty() ? n : dec_stack.top();
            dec_stack.push(i);
        }
        long long res = 0;
        for(int i = 0; i < n; i++) {
            // printf("%d %d, %d %d\n", left_as_max[i], left_as_min[i], right_as_max[i], right_as_min[i]);
            res += (((long long)(i - left_as_max[i]) * (right_as_max[i] - i)) - ((long long)(i - left_as_min[i])*(right_as_min[i] - i))) * nums[i];
        }
        return res;
    }