leetcode 周赛 499

零、背景

这次比赛其实不难，但是我写线段树被卡超时了，显示超出时间限制 947 / 958 个通过的测试用例。
最后各种尝试常数优化，不小心还 WA 一次，然后才通过。

本场题型概览如下。
A 题：前缀和。
B 题：统计排序。
C 题：贪心。
D 题：DP+滑动窗口+线段树。

一、数组中的有效元素

题意：如果一个元素严格大于左侧所有元素或者右侧所有元素，则称为有效元素。
要求按原顺序输出所有有效元素。

思路：前缀和

预处理出前缀最大值和后缀最大值，然后依次判断即可。

二、按频率对元音排序

题意：给一个字符串，要求对元音字符排序。
排序规则：优先按出现的频率排序，频率相同时按首次出现位置排序。

思路：统计排序

按题意，统计每个元音字符的频率和首次出现位置。
然后将 map 转化为数组并按题目要求排序，从而得到排序后的分组元音列表。
最后，遍历字符串，遇到元音，就从排序后的结果集中按顺序取一个元音。

小技巧：排序后对容器翻转，则把获取第一个元素变成获取最后一个元素，从而可以 O(1)删除元音。

三、使数组非递减需要的最小累计值

题意：给一个数组，每次操作可以对一个子数组都加上一个数字。
求怎么操作，才能使得数组非递减有序，且操作的数字之和最小。

思路：贪心

目标是让数组递增，显然，每次操作时选择一个中间子数组，肯定不如选择整个后缀更优。

证明：假设答案中某个操作不是后缀，则把这个操作的后缀都补齐，不影响最终答案。

有了这个推论，就可以推导出贪心算法：每次相邻位置值变小时，下个位置的值就应该加上差值，使得与上个位置的值相等。

四、距离至少为 K 的交替子序列的最大和

题意：给一个数组和正整数 K，如果选择的子序列下标位置差不小于 K 且子序列是严格交替变大变小的，则称为有效子序列。
求有效子序列中子序列元素值之和的最大和。
严格交替变大变小定义：任意相邻三个元素，中间的值要么大于两边的元素，要么小于两边的元素。

思路：动态规划+滑动窗口+线段树

首先很容易想到一个简单的动态规划方程。

状态定义：dp[i][dir] 第 i 个元素作为 dir 序结尾的最大有效子序列和。

状态转移方程：

dp[i][1] = nums[i] + max(dp[j][0]) && j <= i - k && nums[j] < nums[i];
dp[i][0] = nums[i] + max(dp[j][1]) && j <= i - k && nums[j] > nums[i];

方程分两部分。
1）自身就是最大值。
2）前面还有元素，但是交替变大变小的方向需要与当前的相反，且满足大小关系。

复杂度：O(n^2)

优化方向显然在 max(dp[j][dir])。

第一个优化：j 永远比 i 小 k，显然是滑动窗口，窗口外的才参与计算，由此消除 k。

此时，问题转化为了 max(dp[j][dir]) && nums[j] < nums[i]。
对于nums[j] < nums[i]，公式转化为文字就是，求值 nums[j] 小于 nums[i] 的所有位置里，最大的 dp[j][dir]。
对于nums[j] > nums[i]，含义是类似的，这里暂时不重复描述了。

如果把 nums[j] 当做下标，则问题转化为了，求区间 [1, nums[i]-1] 的最大值。
显然可以使用线段树来做。

正常情况下，是需要对 nums[j] 做离散化的。
不过这道题的 nums 值域不大，且都是正整数，可以直接用来当做下标。

由此，我们就可以通过线段树来解决一个维度小于指定值时另一个维度的最值问题。

注意事项：不要从线段树中求最终答案，应该从 max(dp) 中求最终答案。
因为滑动窗口内的答案还没有加入线段树，直接求就会少算一部分，从而导致答案错误。

五、最后

这次比赛最后一题算是稍微复杂一点的题，结合了动态规划、滑动窗口、线段树。
如果把值域设置的大一些，再引入离散化，这道题就完美了。

《完》。

-EOF-

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