LeetCode 2106 摘水果

Ciel Yang 收录于类别练习 OJ解题报告

2023-05-07 2023-05-07 约 1148 字预计阅读 3 分钟

本题的解题思路比较简单，更多考验编码细节，比如：合并冗余代码、起止条件处理等。

题目描述

原题链接如下： LeetCode 2106 摘水果

题目大意

需要摘取的果树必须连续排列在一个区间之内
可能会重复路过同一棵果树，但是只计数一次
上限 k 指的是移动的步数，而不是区间的长度

输入与输出

示例输入有 3 组：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
Input 1:
fruits = [[2,8],[6,3],[8,6]]
startPos = 5
k = 4

Input 2:
fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]]
startPos = 5
k = 4

Input 3:
fruits = [[0,3],[6,4],[8,5]]
startPos = 3
k = 2

对应的输出是：

1
2
3
4
5
6
7
8
Output 1:
9

Output 2:
14

Output 3:
0

解题思路

观察本题特征可以发现，最后采集的果树必定是所有果树序列的子序列，而要处理子序列相关的最值问题，自然要考虑是否能够使用滑动窗口来处理。

注意

滑动窗口对应的区间不是题干中提到的位置数轴，而是果树组成的序列。

第一，必须明确区间之内的移动方式非常简单，区间之内移动时至多发生一次转向，而转向点就是区间的一个端点。因为即使发生多次折返，不断路过同一棵果树也不会增加采集水果的数量，反而浪费了移动步数的上限，不如向区间两端延伸尝试扩展区间。所以，移动方式可以分为两种：

先左后右，区间右端点一定大于出发点
先右后左，区间左端点一定小于出发点

信息

上述分类已经包含了没有折返运动的情况。

第二，需要使用滑动窗口解法时需要处理单调性问题，即固定了一个端点之后，另一个端点移动时是否满足单调性。显然，本题是满足单调性的，因为在固定了区间的右端点之后，不论移动的方式如何，只要左端点继续向外拓展，那么采集总数必定不会缩小，反之则必定不会增加。

第三，使用滑动窗口解法时需要提供区间合法性判断条件，具体到本题中就是：区间合法代表使用任意方法移动最多 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 对应的果树序号，而后从此处开始向右枚举区间右端点。但是，本题中需要累加水果，不如直接从区间的最左端点开始枚举，这样不会影响对左端点的查找（因为一定找不到），反而省略了对左侧区间的预处理求和过程。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
impl Solution {
    pub fn max_total_fruits(fruits: Vec<Vec<i32>>, start_pos: i32, k: i32) -> i32 {
        let mut sum = 0;
        let mut re = 0;
        let start = match fruits.binary_search_by_key(&(start_pos - k), |x| x[0]) {
            Ok(t) => t,
            Err(t) => t,
        };
        let end = match fruits.binary_search_by_key(&(start_pos + k), |x| x[0]) {
            Ok(t) => t + 1,
            Err(t) => t,
        };
        let mut l = start;
        for r in start..end {
            sum += fruits[r][1];
            while l <= r
                && fruits[r][0] - fruits[l][0]
                    + (start_pos - fruits[l][0]).min(fruits[r][0] - start_pos)
                    > k
            {
                sum -= fruits[l][1];
                l += 1;
            }
            re = re.max(sum);
        }
        re
    }
}

目录

LeetCode 2106 摘水果

题目描述

题目大意

输入与输出

解题思路

代码