leetcode 第 349 场算法比赛

零、背景

这次比赛最后一题其实也不难，我敲打比较慢，还错了一次，竟然进入前百名了。

一、既不是最小值也不是最大值

题意：给一个值互不相同的数组，返回既不是最大值也不知最小值的任意一个值，不存在返回 -1。

思路：值互不相同，如果长度小于 3，则没有答案。
否则排序后中间的就是符合要求的答案。

二、执行子串操作后的字典序最小字符串

题意：给一个字符串，可以对任意非空子串向前旋转一次，求怎么操作才能得到字典序最小的字符串。

思路：贪心。

从前到后找到第一个可以旋转变小的起始位置，之后连续的寻找可以旋转变小字符，找不到即结束。

如果从来没找到过，说明输入字符串就是字典序最小的，最后一个字母旋转一次即可。

复杂度：O(n)

三、收集巧克力

题意：给一个巧克力数组，位置代表类型，值代表价格。
现在可以对数组循环右移，操作一次的成本是 X，问操作多少次后买到所有类型巧克力后的成本最低。
注：每个类型的巧克力可以在循环右移之前单独决定选择购买或者不购买。

思路：数据量不大，循环枚举。

先假设所有类型的巧克力都在原始数组购买，并记录每个类型的价格，以及总费用。
之后循环右移一次，判断是否有某个类型的巧克力可以使用更低价格购买，可以了更新对应的价格，并更新总费用。
之后继续循环右移，继续判断是否有更低的价格，以及计算总费用。
全部循环一遍后，就可以得到最低的总费用。

四、最大和查询

题意：给 n 个二维坐标<x,y>，现在询问对于二维坐标<X,Y>， 满足 X<=x && Y<=y 的坐标里，最大的x+y 是多少。

思路：基本思路是枚举比较，询问一次的复杂度是O(n)，所有询问的复杂度就是O(q*n)。

纸上简单推理一下，可以发现，想要快速找到答案，必须将维度从二维降低到一维。

降低二度的方法就是离线处理策略。

先对所有二维坐标和所有询问坐标进行排序（优先按 x 轴，相等了再按 y 轴）。

之后先处理询问里面最小的 x。
如果输入的坐标轴中有比 x 更小的坐标，显然不可能是答案，删除即可。
之后，剩下的所有点 x 都是满足答案的，所以只需要在坐标中找到符合要求的 y 的最大坐标和。
大于等于y 的最大权重值，可以使用线段树来区间查询。

有了上面的思路，这道题就可以做了。

不过需要注意几个细节。

1）对于相同的 y，只需要保留最大的 x，这样线段树上每个点只会有一个答案。

2）y 的值很大，需要进行离散化，离散化时需要考虑询问的 y。
方法也很简单。要么对所有 y 进行离散化，要么对询问的 y 进行二分查找。

PS：y 去重时我使用的 hash，离散化时复用 hash，导致 y 变得无序，WA 了一次。

五、最后

这次比赛没那么难，但是也不简单，算是很经典的线段树题吧。

你是怎么做的呢？

《完》

-EOF-

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