LeetCode 2106 摘水果
本题的解题思路比较简单,更多考验编码细节,比如:合并冗余代码、起止条件处理等。
题目描述
原题链接如下: LeetCode 2106 摘水果
题目大意
- 需要摘取的果树必须连续排列在一个区间之内
- 可能会重复路过同一棵果树,但是只计数一次
- 上限 k 指的是移动的步数,而不是区间的长度
输入与输出
示例输入有 3 组:
|
|
对应的输出是:
|
|
解题思路
观察本题特征可以发现,最后采集的果树必定是所有果树序列的子序列,而要处理子序列相关的最值问题,自然要考虑是否能够使用滑动窗口来处理。
第一,必须明确区间之内的移动方式非常简单,区间之内移动时至多发生一次转向,而转向点就是区间的一个端点。因为即使发生多次折返,不断路过同一棵果树也不会增加采集水果的数量,反而浪费了移动步数的上限,不如向区间两端延伸尝试扩展区间。所以,移动方式可以分为两种:
- 先左后右,区间右端点一定大于出发点
- 先右后左,区间左端点一定小于出发点
第二,需要使用滑动窗口解法时需要处理单调性问题,即固定了一个端点之后,另一个端点移动时是否满足单调性。显然,本题是满足单调性的,因为在固定了区间的右端点之后,不论移动的方式如何,只要左端点继续向外拓展,那么采集总数必定不会缩小,反之则必定不会增加。
第三,使用滑动窗口解法时需要提供区间合法性判断条件,具体到本题中就是:区间合法代表使用任意方法移动最多 k 步可以覆盖区间内的所有点。那么,假设区间左右端点分别是 l
和 r
,那么两种移动方式对应的移动距离为:
- 先左后右:
fruits[r][0] - fruits[l][0] + start_pos - fruits[l][0]
- 先右后左:
fruits[r][0] - fruits[l][0] + fruits[r][0] - start_pos
如果上述两个值都大于 k 则说明区间不合法需要缩小。
第四,移动范围的最左、最右端很好确定分别是 start_pos - k
和 start_pos + k
,但是它们是位置信息不是区间的端点(即果树的序号),需要在果树序列之中使用二分法查找对应的果树序号才可以。
代码
理论上,区间的右端点一定不会小于 start_pos
对应的果树序号,即在上述理论分析找到区间的最左、最右端点之后,还要找到 start_pos
对应的果树序号,而后从此处开始向右枚举区间右端点。但是,本题中需要累加水果,不如直接从区间的最左端点开始枚举,这样不会影响对左端点的查找(因为一定找不到),反而省略了对左侧区间的预处理求和过程。
|
|