2104. 子数组范围和

题目

给你一个整数数组 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
-10^9 <= nums[i] <= 10^9

进阶：你可以设计一种时间复杂度为 O(n) 的解决方案吗？

思路

因为nums长度最多是，因此可以暴力枚举子数组左右边界，同时更新子数组最大最小值，两个for循环#card=math&code=O%28n%5E2%29&id=oGYcK)即可求解。

#card=math&code=O%28n%29&id=EeoS0)的解法不太好想，一看解法是单调栈，果然是想不到。看了一下思路，主要是问题的转换不好想。将范围和转换为所有子数组的最大值之和减去所有子数组的最小值之和，然后计算每个数作为子数组的最大值和最小值的次数即可。

假设左侧最近的比它小的数为，右侧最近的比它小的数为，那么所有以为最小值的子数组数目为%C3%97(i-j)#card=math&code=%28k%E2%80%94i%29%C3%97%28i-j%29&id=Z6OOO)。而获得 左侧和右侧最近的比它小的数的下标，则可以使用单调栈，时间复杂度是#card=math&code=O%28n%29&id=Fd1Zh)。很赞的思路，学习一下。作为最大值同理。

代码

暴力法O(n^2)

class Solution {
    public long subArrayRanges(int[] nums) {
        int n = nums.length;
        long ans = 0;
        for (int i = 0; i < n; i++) {
            int min = nums[i];
            int max = nums[i];
            for (int j = i + 1; j < n; j++) {
                min = Math.min(min, nums[j]);
                max = Math.max(max, nums[j]);
                ans += max - min;
            }
        }
        return ans;
    }
}

单调栈O(n)

理解了思路后，先是去复习了一下84题，单调栈真的是长时间不写就不熟悉了。然后回这道题自己写了一遍，学到很多。

class Solution {
    public long subArrayRanges(int[] nums) {
        int n = nums.length;
        // 求两边最近的比自己大的数，需要一个递减栈
        Deque<Integer> decStack = new ArrayDeque<>();
        // leftFirstHigh[i]表示nums[i]左边最近的 ">=nums[i]" 的元素的下标
        int[] leftFirstHigh = new int[n];
        // rightFirstHigh[i]表示nums[i]右边最近的 ">nums[i]" 的元素的下标
        int[] rightFirstHigh = new int[n];
        for (int i = 0; i < n + 1; i++) {
            // 这里在遍历完数组后，再push一个比所有元素都大的数MAX_VALUE可以保证栈中所有元素出栈
            int num = i == n ? Integer.MAX_VALUE : nums[i];
            while (!decStack.isEmpty() && num > nums[decStack.peek()]) {
                int k = decStack.pop();
                leftFirstHigh[k] = decStack.isEmpty() ? -1 : decStack.peek();
                rightFirstHigh[k] = i;
            }
            decStack.push(i);
        }
        long ans = 0;
        for (int i = 0; i < n; i++) {
            // nums[i]作为子数组的最大值出现了(i - leftFirstHigh[i]) * (rightFirstHigh[i] - i)次
            ans += (long) nums[i] * (i - leftFirstHigh[i]) * (rightFirstHigh[i] - i);
        }
        // 求两边最近的比自己小的数，需要一个递增栈
        Deque<Integer> incStack = new ArrayDeque<>();
        // leftFirstLow[i]表示nums[i]左边最近的 "<=nums[i]" 的元素的下标
        int[] leftFirstLow = new int[n];
        // rightFirstLow[i]表示nums[i]右边最近的 "<nums[i]" 的元素的下标
        int[] rightFirstLow = new int[n];
        for (int i = 0; i <= n; i++) {
            int num = i == n ? Integer.MIN_VALUE : nums[i];
            while (!incStack.isEmpty() && num < nums[incStack.peek()]) {
                int k = incStack.pop();
                leftFirstLow[k] = incStack.isEmpty() ? -1 : incStack.peek();
                rightFirstLow[k] = i;
            }
            incStack.push(i);
        }
        for (int i = 0; i < n; i++) {
            // nums[i]作为子数组的最小值出现了(i - leftFirstLow[i]) * (rightFirstLow[i] - i)次
            ans -= (long) nums[i] * (i - leftFirstLow[i]) * (rightFirstLow[i] - i);
        }
        return ans;
    }
}