算法leetcode

力扣2104-子数组的范围和

字数统计: 2.7k字   |   阅读时长: 11分
, , , ,

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

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的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])

通过动态规划预处理出 dp1 和 dp2 之后，枚举所有区间 R = [i, j]，此时不用再一一枚举 nums[i..j] 找最大值 maxR 和最小值 minR 了，而是直接查询预处理好的 dp1 和 dp2 即可。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(N\log N)$。最后计算答案的时候还是要 $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。

代码 (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
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