力扣2104-子数组的范围和

  |  

摘要: 通过一个问题看分别计算各个元素对答案的贡献的思想

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:潮汐朝夕
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


在文章 面试好题连载 中,我们提到了适合作为面试题的几个标准大致如下:

对于适合面试的题目,以下几个要点中 (1)(2)(5)必须满足,(3)(4)至少满足一个:

(1) 考查基础的数据结构和主流算法,避开邪门算法和脑筋急转弯
(2) 暴力方法很容易想到
(3) 最好有两种以上的优化方式
(4) 最好有两三道递进的题可以放到一起
(5) 最终代码不长

今天我们看一个比较基础的题,leetcode第2104题,【2104. 子数组范围和】。

本题暴力方法很容易,同时有动态规划、单调栈这两种优化方法,都属于主流算法,代码也不长。满足做面试题的条件。另外分别计算各个元素对答案的贡献这种算法思想更值得体会。

下面我们来看一下这个题。

题目描述

给你一个整数数组 nums 。nums 中,子数组的 范围 是子数组中最大元素和最小元素的差值。

返回 nums 中 所有子数组范围的和 。

子数组是数组中一个连续非空的元素序列。

提示

1
2
1 <= nums.length <= 1000
-1e9 <= nums[i] <= 1e9

样例

示例 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

算法

本题的暴力算法就是枚举每个区间 R = [i, j],然后枚举 nums[i..j],把该区间的最大值 maxR 和最小值 minR 找到。然后将答案加上 maxR - minR

动态规划

1
2
3
4
5
6
7
8
9
10
状态定义
dp1[i][j] := [i..j] 上的最大值
dp2[i][j] := [i..j] 上的最小值

初始化
dp1[i][i] = dp2[i][i] = nums[i]

状态转移
dp1[i][j] = max(dp1[i][j - 1], nums[j])
dp2[i][j] = min(dp2[i][j - 1], nums[j])

通过动态规划预处理出 dp1dp2 之后,枚举所有区间 R = [i, j],此时不用再一一枚举 nums[i..j] 找最大值 maxR 和最小值 minR 了,而是直接查询预处理好的 dp1dp2 即可。maxR = dp1[i][j]minR = dp2[i][j]

代码(C++)

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
class Solution {
public:
long long subArrayRanges(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> dp1(n, vector<int>(n)), dp2(n, vector<int>(n));
for(int i = 0; i < n; ++i)
{
dp1[i][i] = nums[i];
dp2[i][i] = nums[i];
}
for(int i = 0; i < n - 1; ++i)
{
for(int j = i + 1; j < n; ++j)
{
dp1[i][j] = max(dp1[i][j - 1], nums[j]);
dp2[i][j] = min(dp2[i][j - 1], nums[j]);
}
}
long long ans = 0;
for(int i = 0; i < n; ++i)
for(int j = i; j < n; ++j)
ans += ((long long)dp1[i][j] - dp2[i][j]);
return ans;
}
};

倍增优化DP

在求 dp1[i][j] 时,我们的转移方式是 max(dp1[i][j - 1], nums[j])

它的意思是我们要找区间 [i, j] 上的最大值时,我们将左区间 [i, j - 1] 的最大值和右区间 [j, j] 上的最大值(就是 nums[j]) 对比一下取较大的。

实际上子区间的选择方式有很多,我们实际上可以选择任意的 i < k <= j,比较两个子区间 [i, k - 1],[k, j] 的最大值。

根据我们在分治算法中的思想,以及主定理的内容。这个 k 选择 i, j 之间的中点是最好的,沿着这个思路走下去的话,我们会走到线段树的内容,就有点搞复杂了。这里我们回到适合本题的优化方式,但是思想与这种取中点进行分治的思想类似。

除了优化转移方式之外,我们还可以用倍增的方式优化状态表示,使得 DP 需要推导的阶段数量减少。这种方式是倍增优化DP,leetcode 上的第 466 题是倍增优化DP 的题目,可以参考 【DP难题】力扣466-统计重复个数

我们以最大值为例,看一下倍增优化 DP 怎样表示状态,以及对应的状态转移是怎么做的。

1
2
3
4
5
6
7
8
状态表示
dp[i][j] := 从nums[i]开始,连续 2^j 个数的最大值

初始化
dp[i][0] = nums[i]

状态转移
dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1])

上面的状态表示和转移说的是。当我们要找 [i, i + 2^j - 1] 上的最大值,我们就比较 [i, i + 2^(j-1) - 1],以及 [i + 2^(j-1), i + 2^(j) - 1] 这两个区间的最大值。

当 dp 预处理完后,我们要找 [l, r] 的最大值时的做法如下:

1
2
int k = log2(r - l + 1);
min(dp[l][k], dp[r - (1 << k) + 1][k])

因为 dp[l][k], dp[r - (1 << k) + 1][k] 分别维护区间 [l, $l + 2^{k} - 1$] 和 [$r - 2^{k} + 1$, r]。而 $l + 2^{k} - 1 \geq r - 2^{k} + 1$,因此查询时的这个做法是对的。

我们可以发现,这两个子区间的长度都是 2^k,跟前面的取中点进行分治的思想类似。

可惜的是使用倍增优化 DP 只是把预处理过程变为 $O(NlogN)$。最后计算答案的时候还是要 $O(N^{2})$ 枚举所有区间,因此无效。

分别计算各元素对答案的贡献 + 单调栈

前面我们考虑的是枚举每个子区间,然后问:该区间的最大值、最小值是多少。为了回答这一问,我们通过 DP 的方式进行预处理优化给定区间找最大值最小值的过程。

我们需要换一个思路。如果枚举每一个点,然后问:该点可以作为多少个子区间的最大值,可以做多少个子区间的最小值。如果我们能高效回答这一问,优化整体的算法就有希望了,因为枚举每个点的时间复杂度是天然地比枚举每个区间更好的。

假设我们考虑到 nums[i],下面我们分析一下如何找到以 nums[i] 为最大值的区间 [l, r] 个数,最小值的情况类似。

首先 [i, i],也就是 l = r = i 的时候肯定是一个,下面就是要问 l 能左走多远,r 能向右走多远。

l 向左走,第一次走到 nums[l] > nums[i] 的时候就不能继续向左走了。

同样地,r 向右走,第一次走到 nums[l] > nums[i] 的时候就不能继续向右走了。

于是区间的左端点的范围是 [l + 1, i],右端点的范围是 [i, r - 1],以 nums[i] 为最大值的区间个数就是 (i - l)(r - i)

但是这里还有个小问题,就是 l 向左走,r 向右走的过程中出现等于 nums[i] 的位置怎么办。

具体走的方式是 l 向左走的时候走到等于 nums[i] 的位置也要停。而 l 向右走的时候走到等于 nums[i] 的位置不停,继续向右走直到大于 nums[i]

以上图为例,nums[i1] = nums[i2] = nums[i3]i1, i2, i3 向右走都走到了 r,因为遇到等于的点是不停的。而 i1, i2, i3 向左走分别走到了 l1, l2, l3,因为走到等于的点也要停。

如果往两边都走到大于才停,那么会使得同时包含 nums[i1], nums[i2], nums[i3] 的大区间重复取了。

如果两边都是走到等于就要停,那么会使得同时包含 nums[i1], nums[i2], nums[i3] 的大区间取不到了。

基于以上分析,对于 nums[i],我们需要知道下面四个信息:

(1) i 往左走第一次走到 >= nums[i] 的位置 l1
(2) i 往右走第一次走到 > nums[i] 的位置 r1
(3) i 往左走第一次走到 <= nums[i] 的位置 l2
(4) i 往右走第一次走到 < nums[i] 的位置 r2

那么 nums[i] 对结果的贡献就是 nums[i] * [(r1 - i)(i - l1) - (r2 - i)(i - l2)]

单调栈是专门维护类似于 i 左边第一个大于 nums[i] 的位置这类信息的数据结构。以前专门写过题目列表以及一些题解。

具体地,维护上面的 (1)(2),用单调递减栈,维护上面的 (3)(4) 维护单调递增栈即可。

枚举 r = 0,1,...,n,在过程中维护单调栈。

对于每个出栈的下标 i,i 出栈后的栈顶元素就是 l,而当前枚举到的下标就是 r。

代码

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
class Solution {
public:
long long subArrayRanges(vector<int>& nums) {
int n = nums.size();
stack<int> st_max; // 单调递减栈
stack<int> st_min; // 单调递增栈
long long ans = 0;
for(int r = 0; r < n; ++r)
{
while(!st_max.empty() && nums[st_max.top()] < nums[r])
{
int i = st_max.top();
st_max.pop();
int l = -1;
if(!st_max.empty())
l = st_max.top();
ans += (long long)nums[i] * (i - l) * (r - i);
}
st_max.push(r);
while(!st_min.empty() && nums[st_min.top()] > nums[r])
{
int i = st_min.top();
st_min.pop();
int l = -1;
if(!st_min.empty())
l = st_min.top();
ans -= (long long)nums[i] * (i - l) * (r - i);
}
st_min.push(r);
}
int r = n;
while(!st_max.empty())
{
int i = st_max.top();
st_max.pop();
int l = -1;
if(!st_max.empty())
l = st_max.top();
ans += (long long)nums[i] * (i - l) * (r - i);
}
while(!st_min.empty())
{
int i = st_min.top();
st_min.pop();
int l = -1;
if(!st_min.empty())
l = st_min.top();
ans -= (long long)nums[i] * (i - l) * (r - i);
}
return ans;
}
};

Share