Leetcode 891. 子序列宽度之和

Posted on In ,

题目描述

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

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

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

 

示例 1： 

输入：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 。

示例 2： 

输入：nums = [2]
输出：0

 

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

解答

注意阅读题目，题目中说的序列/子序列，实际上是集合和子集合。 将集合排序为序列。 对于每一个数字，贡献最大值的情况为加，贡献最小值的情况为减。 每个数字只对其左边的子集合作最大值，对右边的子集合作最小值。

详情见onenote。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    const int mod=1000000007;
    int sumSubseqWidths(vector<int>& nums) {
        long long  ans=0;
        vector<long long> vpow(nums.size(),1);
        for (int i=1;i<nums.size();i++){
            vpow[i]=(vpow[i-1]<<1)%mod;
        }
        sort(nums.begin(),nums.end());
        for (int i=0;i<nums.size();i++){
            ans+=nums[i]*(vpow[i]-vpow[nums.size()-i-1])%mod;
            ans%=mod;
        }
        return ans;
    }
};

【C++】数学（乘法）

假如数组：[2,1,3],因为子序列顺序不会对结果产生影响

比如它的子序列[1], [2], [3], [2,1], [2,3], [1,3], [2,1,3] 跟[1,2,3]的子序列[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]最终结果是一样的

所以我们按照递增排序后讨论，这样每个元素都比它左边大或相等(作为最大值)，比它右边小(作为最小值)

那么我们只需要讨论每个元素左右的贡献值，我们不妨拿数字2作为例子，那么它作为最大值贡献了2i次(i=1,排序后)，作为最小值贡献了2(n-i-1)次,可以用数学归纳证明

(这里略)，注：贡献都包含本身统计，结果相减没影响

结果就是每个数贡献值相加sum(2i-2(n-i-1))*nums[i])

Complexity

  • Time: \(O(nlogn)\)
  • Space: \(O(n)\)

题外话

  • 注意取模分配律