难度中等

给你一个整数数组 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

# 贡献法 + 单调栈

暴力解法：我们可以枚举以下标 $i$ 开头， $j$ 结尾的子数组并在枚举的过程中计算最大元素和最小元素。时间复杂度为 $O(n^2)$ 。

由于需要求解的是子数组最大元素和最小元素的差值总和，可以分开来看

子数组最大元素和最小元素的差值总和 = 子数组最大元素总和 - 子数组最小元素总和

此时可以按照子数组最小元素总和来计算即可。

这里主要说明子数组最大元素总和

对每个数 $nums[i]$ ，算出它是哪些子数组的最大值。

设 $l$ 为左边第一个大于 $nums[i]$ 的元素下标
设 $r$ 为右边第一个大于等于 $nums[i]$ 的元素下标
为什么需要大于等于 $nums[i]$ 呢？

例如： $[22,55,33,55]$

若大于 $i$
- $i = 1$ 时候的其中一个子数组： $[55,33,55],[22,55,33,55]$
- $i = 3$ 时候的其中一个子数组： $[55,33,55],[22,22,33,55]$
重复，则结果会变大。

若大于等于 $i$
- $i = 1$ 时候的其中一个子数组： $[55,33],[22,55,33]$
- $i = 3$ 时候的其中一个子数组： $[33,55]$
则不会出现重复的子数组
根据乘法原理，固定左边为头，固定右边为尾

对结果的贡献值： $(i - l) * (r - i) * nums[i]$

	class Solution {
	public long subArrayRanges(int[] nums) {
	int n = nums.length;
	Deque<Integer> st = new ArrayDeque<>();
	// 哨兵
	st.addFirst(-1);
	long lans = 0;
	// 计算子数组的最大值总和
	for (int r = 0; r <= n; r++) {
	// 当 r 等于 n 时，栈中元素若还有剩余，说明右边没有比当前大的元素，则 r 为 n
	int x = r == n ? Integer.MAX_VALUE : nums[r];
	//[递减元素的下标]
	while (st.size() > 1 && nums[st.peekFirst()] <= x) {
	Integer i = st.pollFirst();
	// 栈顶元素 i 下面的元素就是 l
	Integer l = st.peekFirst();
	lans += (i - l) * (r - i) * (long) nums[i];
	}
	st.addFirst(r);
	}

	st.clear();
	// 哨兵
	st.addFirst(-1);
	long rans = 0;
	// 计算子数组的最小值总和
	for (int r = 0; r <= n; r++) {
	// 当 r 等于 n 时，栈中元素若还有剩余，说明右边没有比当前小的元素，则 r 为 n
	int x = r == n ? Integer.MIN_VALUE : nums[r];
	//[递减元素的下标]
	while (st.size() > 1 && nums[st.peekFirst()] >= x) {
	Integer i = st.pollFirst();
	// 栈顶元素 i 下面的元素就是 l
	Integer l = st.peekFirst();
	rans += (i - l) * (r - i) * (long) nums[i];
	}
	st.addFirst(r);
	}
	return lans - rans;
	}
	}

贡献法单调栈

栈单调栈贡献法

# 贡献法 + 单调栈

子数组最小乘积的最大值

巫师的总力量和