Keshawn_lu's Blog

Leetcode 891. 子序列宽度之和

字数统计: 477阅读时长: 2 min
2022/11/18 Share

题目简介：

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

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

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

示例 1：

1
2
3
4
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 。

示例 2：

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

提示：

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

思路：

由于题目要求的子序列并不需要连续，所以与元素所处的位置无关。

我们计算每个元素所能作出的贡献，因此我们先对数组进行排序。

例如数组[1, 2, 3, 4]，对于3这个元素，它作为子数组最大值的情况便是[3], [1, 3], [2, 3], [1, 2, 3]。

因此对于下标i，作为最大值的个数为2^i，作为最小值的个数为2^(n - i - 1)。

因此对于每个元素nums[i]，其作出的最后贡献为(count[i] - count[n - i - 1]) * nums[i]。

tip:

  • 为防止溢出，需要使用long。

代码如下：

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:
    int sumSubseqWidths(vector<int>& nums) {

        int mod = pow(10, 9) + 7;

        sort(nums.begin(), nums.end());

        vector<int> count(nums.size());

        count[0] = 1;
        for(int i = 1; i < nums.size(); i++){

            count[i] = count[i - 1] * 2 % mod;
        }

        long res = 0;
        for(int i = 0; i < nums.size(); i++){

            res += long(count[i] - count[nums.size() - i - 1]) * nums[i] % mod;
        }

        return (res % mod + mod) % mod;	//res可能为负数，因此需要先 %mod
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网