每日一题 —— LC. 891 子序列的宽度之和
admin
2024-04-12 04:29:19
0次

891. 子序列的宽度之和

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

给你一个整数数组 nums ,返回 nums 的所有非空 子序列 的 宽度之和 。由于答案可能非常大,请返回对 109+710^9 + 7109+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 。

思路

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

此题的数据范围是 10510^5105,也就是 n=105n = 10^5n=105。

暴力是一定行不通的。

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

什么意思呢?就是对于数组中的某个元素,我们计算一下,这个元素作为最小值的子序列,有多少个;这个元素作为最大值的子序列,又有多少个。我们要求的是所有子序列的最大值减最小值的和。那么我们就能算出这个元素对于最终答案的贡献。假设这个元素为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]区间的数,每个数都有保留或者不保留的选择,那么能形成的子序列数量是 2i2^{i}2i;所以以第i个数作为最大值的子序列的个数是 2i2^i2i;同理,对于以第i个数作为最小值的子序列,一定要保留第i个数,对于后面的[i + 1, n - 1]区间内的每个数,都有保留或者不保留的选择,那么能形成的子序列数量是 2n−1−i2^{n - 1 - i}2n−1−i;

那么第i个数对答案的贡献就是 (2i−2n−1−i)×nums[i](2^i-2^{n-1-i}) × nums[i](2i−2n−1−i)×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& 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);}
};

小结

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

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

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

相关内容

热门资讯

蜻蜓订购APP贵金属订购非法期...   蜻蜓订购APP以"投资平台"名义对外宣传,主打贵金属期货(订购)交易。该平台一方面强调自身"正规...
悟空订购APP非法期货交易欺骗...   近期,有投资者反映,“悟空订购APP”等平台以白银、贵金属订购为名,宣传所谓“高收益”“低门槛”...
小赢淘金APP期货投资骗局,平...   “小赢淘金”之流,最擅长的就是用“注册送现金”、“充值返券”的糖衣炮弹来引流。别天真地以为那是福...
八方淘金APP非法期货交易欺骗...   警惕!八方生财、每日淘金、小赢淘金、悟空订购、蜻蜓订购、斗金订购等APP均涉嫌非法期货交易!  ...
智易购APP贵金属订购交易骗局...   很多人看到“3元起投”“充值送福利”“操作简单”“随时提现”这类宣传,很容易把智易购APP当成普...
喜玛银庄APP商品订购投资骗局...   喜玛银庄APP白银、铂金“现货订购”骗局警示:无资质平台涉嫌非法期货交易,投资者爆仓后如何维权?...
吉鑫乐享APP炒贵金属订购交易...   近期,多名投资者反映在“吉鑫乐享APP”进行贵金属投资时遭遇严重亏损,甚至血本无归。看似正规的“...
易掘金APP虚假期货投资骗局,...   “易掘金”的APP它打着“高收益、灵活投资”的旗号,宣称通过“商品订购”就能轻松赚钱,吸引了不少...
在大吉订购APP订购交易亏损被...   近期,不少投资者反映在“大吉订购App”上投资白银、铂金等商品遭遇严重亏损。该平台宣称提供现货订...
铂银壹号APP商品订购交易亏损...   许多中小投资者误以为网上的“商品现货订购”是合规合法的理财渠道,殊不知这背后隐藏着巨大的合规风险...
兴鑫淘金APP贵金属订购交易亏...   白银、贵金属或其他商品类投资,除国家批准的正规期货交易场所及持牌期货公司外,市面上大量第三方交易...
铂银掘金APP无资质的违规平台...   铂银掘金等平台的投资者,往往是被“注册送现金”“充值返现券”“首单免亏”等广告话术吸引,进而下载...
八方淘金APP订购交易不合规,...   “八方淘金APP”“铂银掘金APP”“铂银壹号APP”等软件被指以“现货订购”为名,实际采用高杠...
在指尖订购APP订购商品亏损被...   指尖订购APP这类平台,表面是“订购交易”,实则是披着电商外衣的非法期货陷阱。绝大多数投资者被蒙...
在犀贝易购APP做商品订购交易...   市面上打着“现货投资”“贵金属交易”旗号的APP并不少,但真正合规、受监管的平台并不多。犀贝易购...
易达淘金APP虚假商品订购交易...   易达淘金APP存在严重的虚假宣传与违规交易行为。该平台打着“商品订购”的旗号,实则通过不合规的交...
大浪淘金APP白银订购亏损被骗...   大浪淘金APP最隐蔽的套路,在于其完全封闭的内盘交易系统。表面上,它宣称与国际贵金属市场接轨;实...
一品好购APP上订购白银出现亏...   一品好购APP原名“一品订购”,运营方为上海宝智未来信息技术有限公司。近期不少投资者反映在该平台...
九州订购APP贵金属订购投资骗...   九州订购APP正通过抖.音、快手、今日头条等平台大量投放投资广告,用“5元起投”“充值返现”“0...
坚锅淘金APP交易软件并不正规...   当前,市面上大量所谓的“现货商城订购”交易软件,早已偏离了正常的实物商品买卖,演变为高杠杆、高手...