leetcode 周赛 488

零、背景

这次比赛整体不难，但被卡常数卡爆了，最终掉到几百名之外。

A 题：后缀和
B 题：栈
C 题：线段树或滑动窗口
D 题：三维 DP

最终排名：200+ 名
代码仓库：详见 https://github.com/tiankonguse/leetcode-solutions

一、统计主导元素下标数

题意：给一个数组。若某个元素大于它右侧所有元素的平均值，则称为主导元素。
求主导元素的个数。

思路：后缀和

从后往前计算后缀和（以及后缀元素个数），即可快速计算右侧平均值，从而判断每个元素是否为主导元素。

二、合并相邻且相等的元素

题意：给一个数组，若存在相邻且相等的元素，则将这两个元素替换为它们的和。
每次优先合并最左边的一对。
直到不存在相邻且相等的元素为止。

思路：栈

从左到右遍历数组：若当前元素与栈顶元素相等，则将栈顶元素出栈，并把它的值累加到当前元素。
随后继续与新的栈顶比较，直到不再相等为止。
最后这个累计和元素入栈。

注意事项：可能出现“连锁合并”，需要一直比较到不再相等为止。
例如数据：10 8 4 2 1 1。

三、开销小于等于 K 的子数组数目

题意：给一个数组，求开销小于等于 K 的子数组数目。
开销：子数组最大值与最小值之差，再乘以子数组长度。

思路：线段树或滑动窗口

线段树思路：

开销的一个性质：左端点固定时，右端点越大，开销越大，满足单调性。
因此可枚举左端点，并二分右端点，找到满足条件的最大右端点。
最初版本通过了 765 / 812 个测试用例。

滑动窗口思路：

由于开销随右端点单调不减，可以证明每个左端点对应的边界右端点也具有单调性。
因此可维护最小值单调队列和最大值单调队列，在滑动窗口内维护这两个队列，从而找到满足条件的边界右端点。
耗时：119ms

线段树优化：结合滑动窗口推导出的单调性，二分时左边界可以从上次得到的右边界开始，减少计算量。
耗时：1419ms

四、恰好 K 个下标对的最大得分

题意：给两个数组，下标对的得分为两个数组在对应下标处元素的乘积，求恰好 K 个下标对的最大得分和。
下标对规则：两个数组分别选择 K 个下标，并按下标顺序组成 K 个下标对。

思路：三维动态规划

动态转移方程如下，写三层循环即可。

dp(i,j,k) = max(
  dp(i-1,j-1,k-1) + a[i] * b[j],
  dp(i-1,j,k),
  dp(i,j-1,k),
  dp(i-1,j-1,k)
)

五、最后

这次比赛整体比较简单，但第三题我的线段树被卡常数了，浪费了很多时间。
最后改成单调队列滑动窗口才通过。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号 ID：tiankonguse-code