1.题目

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

  1. 输入：nums = [1,2,3]
  2. 输出：4
  3. 解释：nums 的 6 个子数组如下所示：
  4. [1]，范围 = 最大 - 最小 = 1 - 1 = 0 
  5. [2]，范围 = 2 - 2 = 0
  6. [3]，范围 = 3 - 3 = 0
  7. [1,2]，范围 = 2 - 1 = 1
  8. [2,3]，范围 = 3 - 2 = 1
  9. [1,2,3]，范围 = 3 - 1 = 2
  10. 所有范围的和是 0 + 0 + 0 + 1 + 1 + 2 = 4
  1. 输入：nums = [1,3,3]
  2. 输出：4
  3. 解释：nums 的 6 个子数组如下所示：
  4. [1]，范围 = 最大 - 最小 = 1 - 1 = 0
  5. [3]，范围 = 3 - 3 = 0
  6. [3]，范围 = 3 - 3 = 0
  7. [1,3]，范围 = 3 - 1 = 2
  8. [3,3]，范围 = 3 - 3 = 0
  9. [1,3,3]，范围 = 3 - 1 = 2
  10. 所有范围的和是 0 + 0 + 0 + 2 + 0 + 2 = 4
  1. 输入：nums = [4,-2,-3,4,1]
  2. 输出：59
  3. 解释：nums 中所有子数组范围的和是 59

2.思路

1）暴力思路

遍历所有子数组求相应的子数组内最大值和最小值差之和

2）单调栈

遍历所有子数组求相应的子数组内最大值和最小值差之和,也可以视作所有子数组的最大值之和减去所有子数组的最小值之和。对于num[i]来说，当num[i]作为最小值时，考虑其相应的子数组的个数相乘则得到其相应的总和。遍历之和就可以得到所有子数组的最小值之和。而对于num[i]作为最小时的子数组个数的考虑如下：距离i最近的左侧第一个小于num[i]的数为num[j],右侧为num[k].此时子数组的个数为（i-j)(k-i),和为（i-j)(k-i)*num[i]。那么就需要寻找左侧和右侧第一个小于num[i]的数，记录其下标。这里寻找的过程就会使用到单调栈

3.代码

class Solution {
public:
    long long subArrayRanges(vector<int>& nums) {
        long long ans = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            int minnum = nums[i];
            int maxnum = nums[i];
            for(int j = i+1; j < nums.size(); j++)
            {
                minnum = min(minnum, nums[j]);
                maxnum = max(maxnum, nums[j]);
                ans = ans + maxnum-minnum;
            }
        }
        return ans;
    }
};

class Solution {
public:
    long long subArrayRanges(vector<int>& nums) {
        long long sumMax = 0, sumMin = 0;
        int n = nums.size();
        vector<int> MinLeft(n), MinRight(n), MaxLeft(n), MaxRight(n);
        stack<int> Minstack, Maxstack;
        for(int i = 0; i < nums.size(); i++)
        {
            while(!Minstack.empty()&& nums[Minstack.top()] > nums[i])
            {
                Minstack.pop();
            }

            MinLeft[i] = Minstack.empty()? -1 : Minstack.top();
            Minstack.push(i);
            while(!Maxstack.empty()&&nums[Maxstack.top()] <= nums[i])
            {
                Maxstack.pop();
            }
            MaxLeft[i] = Maxstack.empty()? -1 : Maxstack.top();
            Maxstack.push(i);
        }
        Minstack = stack<int>();
        Maxstack = stack<int>();
        for(int i = nums.size()-1; i >= 0; i--)
        {
            while(!Minstack.empty()&& nums[Minstack.top()] >= nums[i])
            {
                Minstack.pop();
            }

            MinRight[i] = Minstack.empty()? n : Minstack.top();
            Minstack.push(i);
            while(!Maxstack.empty()&&nums[Maxstack.top()] < nums[i])
            {
                Maxstack.pop();
            }
            MaxRight[i] = Maxstack.empty()? n : Maxstack.top();
            Maxstack.push(i);
        }
        for(int i = 0; i < nums.size(); i++)
        {
            sumMin = sumMin+static_cast<long long>(i - MinLeft[i])*(MinRight[i] -i)*nums[i];
            sumMax = sumMax+static_cast<long long>(i - MaxLeft[i])*(MaxRight[i] -i)*nums[i];
        }
        return sumMax - sumMin;
    }

}