题目描述：
给你一个整数数组 nums 。nums 中，子数组的 范围 是子数组中最大元素和最小元素的差值。
返回 nums 中 所有 子数组范围的 和 。
子数组是数组中一个连续 非空 的元素序列。
数据范围：
$1\le nums.len \le 10^3, -10^9 \le nums[i] \le 10^9$
题解：
需要统计子数组中最大值和最小值的差值和。可以考虑分别统计最大值和最小值。
分别统计最大值和最小值就变成了 07. 子数组的最小值之和 | Luobuyu’s Blog 这个问题。
单调栈做法：
使用单调增栈，找出每个元素左右两侧比他小的数。并且该元素可以在这段区间中作为最小值。
使用单调减栈，找出每个元素左右两侧比他大的数。并且该元素可以在这段区间中作为最大值。
dp做法：
也是对最大值最小值分开考虑。
考虑最大值，加入 $nums[i]$ 之后，找出前一个比他大的，下标为 $p$ 。
$dp[i] = dp[p] + (i - p)\times nums[i]$ 。
考虑最小值，加入 $nums[i]$ 之后，找出前一个比他小的，下标为 $p$ 。
$dp[i] = dp[p] + (i - p)\times nums[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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
long long subArrayRanges(vector<int> &nums)
{
int top = -1, n = nums.size();
vector<int> st(n), left(n, -1), right(n, n);
for (int i = 0; i < n; ++i)
{
while (top >= 0 && nums[st[top]] >= nums[i])
{
right[st[top]] = i;
--top;
}
st[++top] = i;
}
top = -1;
for (int i = n - 1; i >= 0; --i)
{
while (top >= 0 && nums[st[top]] > nums[i])
{
left[st[top]] = i;
--top;
}
st[++top] = i;
}
long long ans1 = 0;
for (int i = 0; i < n; ++i)
{
ans1 += 1ll * (i - left[i]) * (right[i] - i) * nums[i];
}
fill(left.begin(), left.end(), -1);
fill(right.begin(), right.end(), n);
top = -1;
for (int i = 0; i < n; ++i)
{
while (top >= 0 && nums[st[top]] <= nums[i])
{
right[st[top]] = i;
--top;
}
st[++top] = i;
}
top = -1;
for (int i = n - 1; i >= 0; --i)
{
while (top >= 0 && nums[st[top]] < nums[i])
{
left[st[top]] = i;
--top;
}
st[++top] = i;
}
long long ans2 = 0;
for (int i = 0; i < n; ++i)
{
ans2 += 1ll * (i - left[i]) * (right[i] - i) * nums[i];
}
return ans2 - ans1;
}
};
|