LC 2104. 子数组范围和
给你一个整数数组 nums 。nums 中，子数组的范围是子数组中最大元素和最小元素的差值。
返回 nums 中 所有 子数组范围的和。
子数组是数组中一个连续 非空 的元素序列。
输入：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
思路：
- 记录每个值
nums[i] 能成为最小值、最大值的次数 min[i], max[i]，子数组范围的和 = nums[i] * (max[i] - min[i])
- 通过单调栈来维护每个值
nums[i] 能成为最小值和最大值的区间，然后就能根据区间的长度求出这个值出现的次数
- 求区间：单调栈
- 求最小值：
- 通过最小栈从左到右来维护当前值能到达的最左区间，记录到 l[i] 中
- 通过最小栈从右到左来维护当前值能达到的最右区间，记录到 r[i] 中
- 整个区间能产生的子区间数为 (i - l[i]) * (r[i] - i)
- 求最大值：
- 通过最大栈从左到右来维护当前值能到达的最左区间，记录到 l[i] 中
- 通过最大栈从右到左来维护当前值能达到的最右区间，记录到 r[i] 中
- 整个区间能产生的子区间数为 (i - l[i]) * (r[i] - i)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
class Solution {
int n;
public long subArrayRanges(int[] nums) {
n = nums.length;
long[] min = getCnt(nums, true), max = getCnt(nums, false);
long res = 0;
for (int i = 0; i < n; i++) {
res += nums[i] * (max[i] - min[i]);
}
return res;
}
long[] getCnt(int[] nums, boolean isMin) {
long[] l = new long[n], r = new long[n], ans = new long[n];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && (isMin ? nums[stack.peek()] >= nums[i] : nums[stack.peek()] <= nums[i])) {
stack.pop();
}
l[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(i);
}
stack.clear();
for (int i = n - 1; i >= 0; i--) {
while (!stack.isEmpty() && (isMin ? nums[stack.peek()] > nums[i] : nums[stack.peek()] < nums[i])) {
stack.pop();
}
r[i] = stack.isEmpty() ? n : stack.peek();
stack.push(i);
}
for (int i = 0; i < n; i++) {
ans[i] = 1l * (i - l[i]) * (r[i] - i);
}
return ans;
}
}
|