每日一题 —— LC. 891 子序列的宽度之和

891. 子序列的宽度之和

一个序列的 宽度 定义为该序列中最大元素和最小元素的差值。

给你一个整数数组 nums ，返回 nums 的所有非空 子序列 的 宽度之和 。由于答案可能非常大，请返回对 $10^9+7$ 取余 后的结果。

子序列 定义为从一个数组里删除一些（或者不删除）元素，但不改变剩下元素的顺序得到的数组。例如，[3,6,2,7] 就是数组 [0,3,1,6,2,2,7] 的一个子序列。

提示：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

示例

输入：nums = [2,1,3]
输出：6
解释：子序列为 [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3] 。
相应的宽度是 0, 0, 0, 1, 1, 2, 2 。
宽度之和是 6 。
1
2
3
4
5

思路

暴力是人类最直观的思维，如果要暴力来做，那么就是枚举所有的子序列，然后依次计算每个子序列中的最大值和最小值，求出每个子序列的宽度，然后进行累加。假设数组的长度为n，那么所有子序列的数量就是$2^n$，因为生成一个子序列，就是对每个元素进行选择：保留or删除。每个元素有2种选择，则n个元素就一共有 $2^n$ 种方案。

此题的数据范围是 $10^5$，也就是 $n=10^5$。

暴力是一定行不通的。

此时我们转换思维，不从子序列来推最小值最大值，而从最小值最大值来推子序列。

什么意思呢？就是对于数组中的某个元素，我们计算一下，这个元素作为最小值的子序列，有多少个；这个元素作为最大值的子序列，又有多少个。我们要求的是所有子序列的最大值减最小值的和。那么我们就能算出这个元素对于最终答案的贡献。假设这个元素为a，以a作为最小值的子序列共有L个，以a作为最大值的子序列共有R个，那么该元素对答案的贡献就是 a × (R - L)

我们只要对数组中每个元素，计算一下其对答案的贡献，然后进行一下累加即可。

---

关键点一：不从子序列来推最小值最大值，而从最小值最大值来推子序列

---

然后，对于某个子序列，我们只关心它的两个最值，那么子序列内部元素的顺序就无关紧要。比如，子序列 1 3 5 7和子序列5 7 3 1，我们其实可以将其看成等价，这并不会影响最终答案的正确性。

所以，我们可以对整个数组先排个序。

为什么要排序呢？因为排序后能够很方便的计算某个元素作为最大值和最小值的子序列的个数！

---

关键点二：顺序无关

---

排完序后，对于某个位置i的数，它比[0， i - 1]的所有数都大，比[i + 1, n - 1]的所有数都小。（这里其实不是严格的大小关系，因为有可能存在相等的元素）。

也就是说，[0, i]中第i个数是最大值（可能有相等的但不影响），[i, n - 1]中第i个数是最小值。

由于某个子序列，是保留一些数，和删去一些数。那么第i个数作为最大值的子序列，一定需要保留第i个数，对于前面的[0, i - 1]区间的数，每个数都有保留或者不保留的选择，那么能形成的子序列数量是 $2^i$；所以以第i个数作为最大值的子序列的个数是 $2^i$；同理，对于以第i个数作为最小值的子序列，一定要保留第i个数，对于后面的[i + 1, n - 1]区间内的每个数，都有保留或者不保留的选择，那么能形成的子序列数量是 $2^{n-1-i}$；

那么第i个数对答案的贡献就是 $(2^i-2^{n-1-i})\times nums[i]$

---

关键点三：排序后，推公式

---

所以，我们可以进行一次遍历，挨个累加每个元素的贡献，就能得到最终的答案

// C++
typedef long long LL;
const int MOD = 1e9 + 7;
class Solution {
public:

    // 快速幂
    LL qmi(LL a, LL b, LL p) {
        LL t = a, ans = 1;
        while (b) {
            if (b & 1) ans = (ans * t) % p;
            b >>= 1;
            t = (t * t) % p;
        }
        return ans;
    }

    // 每个值作为最小值的序列个数
    // 每个值最为最大值的序列个数
    // 计算每个值对答案的贡献
    int sumSubseqWidths(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        LL mi = 0, ma = 0; // 最小值的和, 最大值的和
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            // 组合数求和Cn0+Cn1+...+Cnn = 2^n
            // nums[i]作为最大值的子序列个数
            ma = (ma + qmi(2, i, MOD) * nums[i]) % MOD;
            // nums[i]作为最小值的子序列个数
            mi = (mi + qmi(2, n - 1 - i, MOD) * nums[i]) % MOD;
        }
        return (int) ((ma - mi + MOD) % MOD);
    }
};
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

小结

本题是上周五的每日一题。

当按正向的直观的逻辑无法求解时，可以逆向思考，考虑单个元素对整体答案的贡献值。

运用这样思维的题目，还有10月底某天的每日一题（907. 子数组的最小值之和），以及今天（2022/11/24）的每日一题（795. 区间子数组个数），这两道题都可以采用这样的思维，加上单调栈，进行求解。