2104.子数组范围和

链接：2104.子数组范围和
难度：Medium
标签：栈、数组、单调栈
简介：给你一个整数数组 nums 。nums 中，子数组的 范围 是子数组中最大元素和最小元素的差值。返回 nums 中 所有 子数组范围的 和 。

题解 1 - cpp

• 编辑时间：2022-03-04
• 执行用时：12ms
• 内存消耗：11.5MB
• 编程语言：cpp
• 解法介绍：单调栈，把子数组求和变换为，所有子数组的最大值求和减去最小值求和。

class Solution {
   public:
    struct node {
        int minl, maxl, minr, maxr, idx, num;
    };
    long long subArrayRanges(vector<int>& nums) {
        long long ans = 0;
        int n = nums.size();
        stack<int> mins, maxs;
        vector<node> list(n);
        for (int i = 0; i < n; i++) {
            list[i].idx = i;
            list[i].num = nums[i];
            while (mins.size() && nums[mins.top()] > nums[i]) {
                list[mins.top()].minr = i;
                mins.pop();
            }
            list[i].minl = mins.size() ? mins.top() : -1;
            while (maxs.size() && nums[maxs.top()] < nums[i]) {
                list[maxs.top()].maxr = i;
                maxs.pop();
            }
            list[i].maxl = maxs.size() ? maxs.top() : -1;
            mins.push(i);
            maxs.push(i);
        }
        while (mins.size()) {
            list[mins.top()].minr = n;
            mins.pop();
        }
        while (maxs.size()) {
            list[maxs.top()].maxr = n;
            maxs.pop();
        }
        for (int i = 0; i < n; i++) {
            ans += (long long)(list[i].maxr - i) * (i - list[i].maxl) *
                   list[i].num;
            ans -= (long long)(list[i].minr - i) * (i - list[i].minl) *
                   list[i].num;
        }
        return ans;
    }
};