来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-of-subarray-ranges
题目描述
给你一个整数数组 nums 。nums 中，子数组的 范围 是子数组中最大元素和最小元素的差值。
返回 nums 中 所有 子数组范围的 和 。
子数组是数组中一个连续 非空 的元素序列。
示例 1： 输入：nums = [1,2,3] 输出：4 解释：nums 的 6 个子数组如下所示： [1]，范围 = 最大 - 最小 = 1 - 1 = 0 [2]，范围 = 2 - 2 = 0 [3]，范围 = 3 - 3 = 0 [1,2]，范围 = 2 - 1 = 1 [2,3]，范围 = 3 - 2 = 1 [1,2,3]，范围 = 3 - 1 = 2 所有范围的和是 0 + 0 + 0 + 1 + 1 + 2 = 4 示例 2： 输入：nums = [1,3,3] 输出：4 解释：nums 的 6 个子数组如下所示： [1]，范围 = 最大 - 最小 = 1 - 1 = 0 [3]，范围 = 3 - 3 = 0 [3]，范围 = 3 - 3 = 0 [1,3]，范围 = 3 - 1 = 2 [3,3]，范围 = 3 - 3 = 0 [1,3,3]，范围 = 3 - 1 = 2 所有范围的和是 0 + 0 + 0 + 2 + 0 + 2 = 4 示例 3： 输入：nums = [4,-2,-3,4,1] 输出：59 解释：nums 中所有子数组范围的和是 59 提示： 1 <= nums.length <= 1000 -109 <= nums[i] <= 109
解题思路
首先看数据范围，可以通过暴力法来做，遍历子数组，分别求出最大值最小值然后求和，时间复杂度是O(n2)
还有一种巧妙的方法可以将时间复杂度压缩到O(n)。
对于第i个数ai，如果左边第一个比他小的数下标为left，第一个比他小的数下标位right，那么(left，right)中所有的子数组最小值都是ai，在(left，right)中共有(right - i) * (i - left) 个子数组，那么(left, right)范围内子数组最小值的和为(right - i) * (i - left) * ai，同理可以求出(left, right)范围内子数组最大值的和，两个相减就可以求出(left, right)范围内的范围和。
问题转化为了如何第i个数左边小值和大值及右边的小值和大值，使用单调栈一次遍历便可以分别求得这四个值，并且用vector将下标存起来。
代码展示
暴力法：
class Solution { public: long long subArrayRanges(vector<int>& nums) { int n = nums.size(); long long ret = 0; for (int i = 0; i < n; i++) { int minVal = INT_MAX, maxVal = INT_MIN; for (int j = i; j < n; j++) { minVal = min(minVal, nums[j]); maxVal = max(maxVal, nums[j]); ret += maxVal - minVal; } } return ret; } };
单调栈+数学：
class Solution { public: long long subArrayRanges(vector<int>& nums) { int n = nums.size(); long long ret = 0; vector<int> viLeftMin(n), viRightMin(n), viLeftMax(n), viRightMax(n); stack<int> siMax, siMin; for(int i = 0; i < n; i++) { while(!siMin.empty() && nums[siMin.top()] > nums[i]) siMin.pop(); viLeftMin[i] = siMin.empty()? -1: siMin.top(); siMin.push(i); while(!siMax.empty() && nums[siMax.top()] <= nums[i]) siMax.pop(); viLeftMax[i] = siMax.empty()? -1: siMax.top(); siMax.push(i); } siMax = stack<int>(); siMin = stack<int>(); for(int i = n - 1; i >= 0; i--) { while(!siMin.empty() && nums[siMin.top()] >= nums[i]) siMin.pop(); viRightMin[i] = siMin.empty()? n: siMin.top(); siMin.push(i); while(!siMax.empty() && nums[siMax.top()] < nums[i]) siMax.pop(); viRightMax[i] = siMax.empty()? n: siMax.top(); siMax.push(i); } for(int i = 0; i < n; i++) { ret += ((((long long)viRightMax[i] - i) * (i - viLeftMax[i])) - (((long long)viRightMin[i] - i) * (i - viLeftMin[i])))* nums[i]; } return ret; } };
运行结果
