更新题目 3413. Maximum Coins From K Consecutive Bags
题目 lc3413 · 修改（rev 6） · · 2026-10-27 00:33
body
@@ -1,59 +1,58 @@ ## 题目 -袋子排成一行，编号从 1 开始，每个整数编号对应一个袋子。输入是整数 `k` 和一个 n×3 的数组 `segment`。`segment` 的每一行 `[l, r, money]` 描述一段（segment）：编号从 `l` 到 `r`（两端都包含）的每个袋子里都装着 `money` 这么多钱。各段之间互不相交；不属于任何一段的袋子里没有钱，金额是 0。要求恰好取 `k` 个编号连续的袋子，问最多能拿到多少钱。 +袋子排成一行，编号从 1 开始，每个整数编号对应一个袋子。输入是整数 `k` 和一个 n×3 的数组 `segment`。`segment` 的每一行 `[l, r, money]` 描述一段（segment）：编号从 `l` 到 `r`（两端都包含）的每个袋子里都装着 `money` 这么多钱。各段之间互不相交。不属于任何一段的袋子里没有钱，金额是 0。要求恰好取 `k` 个编号连续的袋子，问最多能拿到多少钱。 -**样例**（原帖和截图里给的都是这一组）：`k = 5`，`segment = [[1,4,2],[6,6,5],[7,7,7],[9,10,1]]`。把各段展开，袋子 1 到 10 的金额依次是 2、2、2、2、0、5、7、0、1、1，其余袋子都是 0。连续取 `k` 个袋子，相当于在这一排上放一个窗口（window），也就是一段连续的编号。只看上面列出的这些袋子，长度为 5 的窗口的金额分别是 [1–5] = 8，[2–6] = 11，[3–7] = 16，[4–8] = 14，[5–9] = 13，[6–10] = 14。其中最大的是取 3 到 7 号（2+2+0+5+7），答案是 16。 +连续取 `k` 个袋子，相当于在这一排上放一个长度为 `k` 的窗口（window）。下面用 [a–b] 表示从 a 号到 b 号的窗口。 + +**样例**（原帖给的就是这一组）：`k = 5`，`segment = [[1,4,2],[6,6,5],[7,7,7],[9,10,1]]`。展开以后，袋子 1 到 10 的金额依次是 2、2、2、2、0、5、7、0、1、1，其余袋子都是 0。长度为 5 的窗口里，[1–5] = 8，[2–6] = 11，[3–7] = 16，[4–8] = 14，[5–9] = 13，[6–10] = 14。最大的是 [3–7]（2+2+0+5+7），答案是 16。 [LeetCode 原题](https://leetcode.com/problems/maximum-coins-from-k-consecutive-bags/) -**Amazon OA 版和 LeetCode 原题的差别** +### Amazon OA 版和 LeetCode 原题的差别 -- 题目背景换成了「亚马逊财务团队的分析师面对无限个袋子」，题名改成 Maximum Money in K Consecutive Bags，要实现的函数是 `calculateMaximumConsecutiveSum(k, segment)`，参数顺序是 `k` 在前。 -- 答案要对 10^9+7 取模（modulo），LeetCode 原题不取模。 -- 面经里贴出的数据范围是 1 ≤ n ≤ 2×10^5，1 ≤ k ≤ 10^9，1 ≤ l ≤ r ≤ 10^9，1 ≤ money ≤ 10^6，并且保证任意两段不相交。题面没说输入的段已经按起点排好序，所以下面按无序输入处理【推断】。 +- 题目背景换成了「亚马逊财务团队的分析师面对无限个袋子」，题名是 Maximum Money in K Consecutive Bags，要实现的函数是 `calculateMaximumConsecutiveSum(k, segment)`，`k` 在前。 +- 答案要对 $10^9+7$ 取模（modulo），LeetCode 原题不取模。 +- 数据范围是 $1 \le n \le 2 \times 10^5$，$1 \le k \le 10^9$，$1 \le l \le r \le 10^9$，$1 \le money \le 10^6$。题面没说输入已经按起点排好序，下面按无序输入处理【推断】。 -**题意有两处不够明确，下面说明按哪种理解实现** +### 题意里不明确的两处 -- 第一处是取模的时机。这里按「先在真实总和里找最大值，最后再对 10^9+7 取模」来实现【推断】。之所以要分清先后，是因为窗口总和最大能到 10^9 × 10^6 = 10^15，比模数大得多，先取模再比大小可能选错窗口（反例见「易错点」）。 -- 第二处是编号是不是从 1 开始。LeetCode 原题的袋子铺满整条数轴，OA 写的是从 1 号到无穷。这两种理解的答案相同：金额都非负，如果窗口有一部分伸到 1 号左边，那部分全是 0，把窗口挪成 [1, k] 不会变差。后面用暴力解（brute force）在随机小数据上对比结果（对拍）时，也按这两种理解各比了一遍，逐组结果一致。 +- **什么时候取模**。窗口总和最大能到 $10^9 \times 10^6 = 10^{15}$，比模数大得多。这里按「先在真实总和里找最大值，最后再取模」实现【推断】。先取模再比大小会选错窗口，反例见「易错点」第二条。 +- **编号从 1 开始还是铺满整条数轴**。OA 写的是从 1 号到无穷，LeetCode 原题是整条数轴。两种理解的答案相同：金额都非负，窗口伸到 1 号左边的那部分全是 0，把窗口挪成 [1–k] 不会变差。下面的对拍按两种理解各比了一遍，结果一致。 ## 面经里怎么考的 -[[c:amazon]] 2026 年从年初到 9 月的 SDE 和 SDE II OA 都考过这道题，通常是编程部分的第一题（Question 1）。考生大多是在职跳槽，也有应届硕士（只拍了题面截图）。贴了英文题面或截图的几篇，用的都是同一个「财务团队」的题目背景；其中一篇贴全了函数签名、数据范围和逐个袋子的金额表，Python 模板是 `def calculateMaximumConsecutiveSum(k, segment):`。 +[[c:amazon]] 2026 年 5 月到 9 月的 SDE、SDE II OA 都考过这道题，通常是编程部分的第一题。考生大多是在职跳槽，也有应届硕士。贴了题面或截图的几篇，用的都是「财务团队」这个题目背景。截图和一篇通过的帖子都写明答案要对 $10^9+7$ 取模。 -- 2026 年 4–6 月，一位在职跳槽的 SDE II 写明了时间安排：算法题限时 40 分钟，后面是 60 分钟的 AI 调试（拿到一个现成的代码项目，修掉里面的 bug，具体情况见本节最后一段），另外还有性格测试，整场下来很累。发帖人没说这道题通过了多少个测试用例（test case）。回复里有人说测试用例有十多个，数据看起来很大。按其他几篇贴出的范围，坐标和 k 都能到 10^9，逐个袋子枚举肯定超时。 -- 一位通过的在职考生说，两道题连同调试一共二十多分钟写完。这位考生点出的考点是：坐标能到 1e9，必须按段计算，也就是坐标压缩（coordinate compression，把稀疏的大坐标映射成连续的小下标，只在这些关键位置上计算）；然后配合前缀和（prefix sum），再用二分查找（binary search）或双指针（two pointers）。窗口的起点或终点落在某一段中间时，这一段只能算被盖住的那一部分；从整段金额里扣掉没盖住的那半段时，要小心乘法的运算符优先级。 -- 也有没通过的。一篇帖子开头的结果标签是 Fail，发帖人贴了完整题面、样例和一句题意概括，但没写卡在哪里；回复里有人说自己刚做完，也觉得这个 OA 挺难。 -- 还有几篇信息很少：有的只留了一句题意，有的只有一张截图（截图在样例表那里截断了，没拍到答案），都没写解法，结果标签都是 WaitingList。 - -同一场 OA 里，算法题后面接的 AI 调试环节，每个人拿到的项目各不相同。有人拿到的是一个类似 Jira 的 issue 评论系统，这位考生选的是 Java Spring Boot。问题是创建、更新评论之后不显示，修的时候要按 README 里写的接口约定（API contract）返回 401/403 和规定的成功状态码（status code），测试只检查 status code 和 message。有人拿到的是后端 API 的问题，导致 dashboard 上没法新建 issue。还有人拿到的是租车 app 的 Node.js 后端，里面有三个互不相关的 bug。另有一篇提到这场 OA 还有 Work Simulation，也就是模拟实际工作情境、让考生做判断的环节；这一篇里要给项目的下一步行动打分，还要给 5 种 vote storage 方案（投票怎么存储）打分。详见 [[q:amazon-oa-ai-debug]]。 +- 5 月一位 SDE II 写了完整题意和样例 16。算法题限时 40 分钟，后面是 60 分钟的 AI 调试（拿到一个现成的代码项目修 bug，详见 [[q:amazon-oa-ai-debug]]），另外还有性格测试。发帖人没说这道题过了多少测试用例（test case），回复里有人说测试用例有十多个，数据看起来很大。 +- 一位通过的考生说，两道题连同调试一共二十多分钟写完。他点出的考点是：坐标能到 $10^9$，必须按段计算，再配合前缀和（prefix sum）加二分查找或双指针（two pointers）。窗口一端落在某段中间时，这一段只能算被盖住的那部分，从整段金额里扣掉没盖住的部分时，要小心乘法的运算符优先级。 +- 也有挂了的。那篇帖子贴了题面和样例，没写卡在哪一步，回复里有人说自己刚做完，也觉得这个 OA 挺难。另外两篇只留了一句题意或一张截图（截图没拍到样例的答案），结果是 waiting list。 ## 思路 -### 为什么只能按段计算 +### 只能按段计算 -坐标和 `k` 都能到 10^9。如果把每个袋子展开、逐个模拟窗口，要处理的袋子数量也是这个量级，一定超时，所以只能以「段」为单位计算。面经里说的「坐标压缩」在这里很简单：只在各段的端点上计算。把段按起点排好序以后，这些段本身就相当于压缩后的坐标，不需要另外建一个映射数组。 +坐标和 `k` 都能到 $10^9$，逐个袋子模拟窗口一定超时，所以只能以「段」为单位算。面经里说的坐标压缩（coordinate compression，只在少数关键坐标上计算）在这里就是：只看各段的端点。 -### 总能找到一端贴着段边界的最优窗口 +### 关键一步：最优窗口总有一端贴着段边界 -关键结论是：一定存在一个最优窗口，它的左端恰好落在某一段的起点 `l`，或者右端恰好落在某一段的终点 `r`。理由分两种情况： +一定存在一个最优窗口，它的左端是某一段的起点 `l`，或者右端是某一段的终点 `r`。分两种情况看任意一个窗口： -- 如果窗口最左边的袋子是空的，把窗口整体右移一格不会变差，因为左边丢掉的是 0，右边新加进来的袋子金额不小于 0。同理，如果窗口最右边的袋子是空的，就把窗口左移一格。 -- 如果窗口两端的袋子都有钱，而且左端不在某段的起点、右端也不在某段的终点，那么窗口右移一格时，总和的变化量是「右端所在段的金额 − 左端所在段的金额」；左移一格的变化量正好是它的相反数。两个相反数里总有一个是非负的，所以总有一个方向挪了不会变差。沿着这个方向一直挪，直到左端碰上某段的起点、或者右端碰上某段的终点为止。 +- 窗口最左边的袋子是空的：整体右移一格，丢掉的是 0，新加进来的不小于 0，不会变差。最右边的袋子是空的，同理左移一格。 +- 两端的袋子都有钱，左端又不在段起点、右端也不在段终点：右移一格，总和变化「右端所在段的金额 − 左端所在段的金额」。左移一格的变化量正好是它的相反数。两者总有一个非负，就往那个方向挪。 -所以只需要检查 2n 个候选窗口：每一段贡献两个，一个以这段的起点为左端，一个以这段的终点为右端。 +两种情况都能一直挪下去而不变差，直到左端碰上某段起点或右端碰上某段终点。所以只要检查 2n 个候选窗口：每段一个以它的起点为左端的窗口，一个以它的终点为右端的窗口。 -### 怎么算每个候选窗口 +两个方向都要看，因为各段金额不同。样例里只看「左端对齐段起点」的窗口，最多找到 [1–5] 和 [6–10] 的 14，找不到右端对齐 7 号的 [3–7]。不加权的版本 LeetCode 2271（Maximum White Tiles Covered by a Carpet）每块瓷砖价值相同，两端都有瓷砖时左移的变化量是 0，那道题只看左端对齐就够了。 -下面用到 Python 标准库 `bisect` 里的两个二分查找函数：在有序列表里找 `x`，`bisect_right` 返回最后一个 `<= x` 的元素之后的位置，`bisect_left` 返回第一个 `>= x` 的元素的位置。 +> [!say] Both coordinates and k go up to 1e9, so I work segment by segment. Some optimal window either starts at a segment's start or ends at a segment's end. If neither edge is on a boundary, sliding one step right or one step left changes the sum by opposite amounts, so one direction never hurts, and I keep sliding until an edge hits a boundary. That leaves 2n candidate windows. -1. 把段按 `l` 排序，分别记下起点列表 `starts` 和终点列表 `ends`。段互不相交，所以按起点排好序以后，终点也是升序的，`ends` 也能直接二分。再算前缀和 `pre[t]`，表示前 `t` 段的完整金额之和，每段的完整金额是 `(r - l + 1) * c`（`c` 就是这段的 `money`）。有了前缀和，连续若干段的完整金额用两个前缀和相减就能直接得到，不用逐段累加。 -2. 以第 `i` 段的起点 `l_i` 为左端的窗口，右端是 `end = l_i + k - 1`。用 `j = bisect_right(starts, end) - 1` 找到最后一个起点还在窗口内的段；第 `i` 段自己的起点就在窗口里，所以 `j` 一定 `>= i`。第 `i` 到第 `j - 1` 段完整落在窗口里，第 `j` 段可能只被盖住前半截，只算被盖住的部分。窗口金额是 `pre[j] - pre[i] + (min(r_j, end) - l_j + 1) * c_j`。 -3. 以第 `i` 段的终点 `r_i` 为右端的窗口，左端是 `start = r_i - k + 1`。用 `j = bisect_left(ends, start)` 找到第一个终点 `>= start` 的段，也就是最左边一个和窗口有重叠的段；第 `i` 段自己的终点就满足条件，所以 `j` 一定 `<= i`。第 `j + 1` 到第 `i` 段完整落在窗口里，第 `j` 段只算被盖住的后半截。窗口金额是 `pre[i + 1] - pre[j + 1] + (r_j - max(l_j, start) + 1) * c_j`。 -4. 所有候选窗口取最大值，**最后**才 `% (10^9 + 7)`，原因见「题目」一节里取模时机的说明。 +### 怎么算一个候选窗口 + +1. 把段按 `l` 排序，记下起点列表 `starts` 和终点列表 `ends`。段互不相交，按起点排好以后终点也是升序，两个列表都能二分。再算前缀和 `prefix[t]`，表示前 `t` 段的整段金额之和，一段的整段金额是 `(r - l + 1) * money`。连续若干段的整段金额就是两个前缀和相减。 +2. 以第 `i` 段起点为左端的窗口是 [`l_i`–`win_end`]，`win_end = l_i + k - 1`。用 `bisect_right(starts, win_end) - 1` 找最后一个起点在窗口内的段，记为 `j`。第 `i` 段的起点就在窗口里，所以 `j >= i`。第 `i` 到第 `j - 1` 段整段落在窗口里，第 `j` 段只算被盖住的前半截，长度是 `min(r_j, win_end) - l_j + 1`。 +3. 以第 `i` 段终点为右端的窗口是 [`win_start`–`r_i`]，`win_start = r_i - k + 1`。用 `bisect_left(ends, win_start)` 找第一个终点不小于 `win_start` 的段，也就是最左边一个和窗口重叠的段，记为 `j`。第 `i` 段自己满足条件，所以 `j <= i`。第 `j + 1` 到第 `i` 段整段在内，第 `j` 段只算后半截，长度是 `r_j - max(l_j, win_start) + 1`。 +4. 2n 个候选取最大值，最后才对 $10^9+7$ 取模。 ## 代码 - -下面是 Python 实现，已运行。验证包括：原帖样例；「测试用例」一节里的边界用例；2000 组随机小数据，和暴力解逐组对比结果（对拍）；以及 n = 2×10^5 的大数据计时。全部通过。 ```python @@ -64,29 +63,31 @@ def calculateMaximumConsecutiveSum(k, segment): - segs = sorted(segment) # 输入不保证有序，先按起点排 - n = len(segs) - starts = [s[0] for s in segs] - ends = [s[1] for s in segs] - pre = [0] * (n + 1) # pre[t] = 前 t 段的完整金额之和 - for i, (l, r, c) in enumerate(segs): - pre[i + 1] = pre[i] + (r - l + 1) * c + segs = sorted(segment, key=lambda seg: seg[0]) # 输入不保证有序，按起点排 + starts = [l for l, _, _ in segs] + ends = [r for _, r, _ in segs] # 段互不相交，所以 ends 也升序 + prefix = [0] # prefix[t] = 前 t 段的整段金额之和 + for l, r, money in segs: + prefix.append(prefix[-1] + (r - l + 1) * money) best = 0 - for i, (l, r, c) in enumerate(segs): - # 1) 窗口左端对齐第 i 段起点：[l, l + k - 1] - end = l + k - 1 - j = bisect_right(starts, end) - 1 # 最后一个起点在窗口内的段，j >= i - lj, rj, cj = segs[j] - total = pre[j] - pre[i] + (min(rj, end) - lj + 1) * cj - best = max(best, total) + for i, (l, r, _) in enumerate(segs): + best = max(best, + window_from_start(segs, starts, prefix, i, l + k - 1), + window_to_end(segs, ends, prefix, i, r - k + 1)) + return best % MOD # 先比真实总和，最后才取模 - # 2) 窗口右端对齐第 i 段终点：[r - k + 1, r] - start = r - k + 1 - j = bisect_left(ends, start) # 第一个终点在窗口内的段，j <= i - lj, rj, cj = segs[j] - total = pre[i + 1] - pre[j + 1] + (rj - max(lj, start) + 1) * cj - best = max(best, total) - return best % MOD # 先比真实总和，最后才取模 +def window_from_start(segs, starts, prefix, i, win_end): + """窗口 [l_i, win_end]：第 i..j-1 段整段在内，第 j 段可能只盖住前半截。""" + j = bisect_right(starts, win_end) - 1 # 最后一个起点 <= win_end 的段，j >= i + lj, rj, mj = segs[j] + return prefix[j] - prefix[i] + (min(rj, win_end) - lj + 1) * mj + + +def window_to_end(segs, ends, prefix, i, win_start): + """窗口 [win_start, r_i]：第 j+1..i 段整段在内，第 j 段可能只盖住后半截。""" + j = bisect_left(ends, win_start) # 第一个终点 >= win_start 的段，j <= i + lj, rj, mj = segs[j] + return prefix[i + 1] - prefix[j + 1] + (rj - max(lj, win_start) + 1) * mj @@ -94,84 +95,37 @@ ``` -如果要在 LeetCode 上提交，需要去掉最后的取模（原题不取模），并把参数改成 LeetCode 给的函数签名。 +`k` 比所有段的总跨度还大时不用特判：`win_end` 超过所有起点，二分落到最后一段，`min(rj, win_end)` 取到 `rj`，整段计入。在 LeetCode 上提交时去掉最后的取模，参数改成原题的签名。 + +2026-10-27 用 Python 3.13 跑过上面这段代码： + +- 样例输出 16。 +- 和逐个袋子枚举的暴力解对拍 2000 组随机小数据（n 取 1 到 6，坐标到 40，`k` 取 1 到 45，金额 1 到 10，含单袋段、相邻段和乱序输入），暴力解按「从 1 号开始」和「整条数轴」各写一版，三者全部一致。 +- 边界用例：`k = 1` 得 7（单袋最大值），`k = 100` 得 22（全部拿到），两段相邻 `k=4, [[1,2,3],[3,4,5]]` 得 16，窗口盖不住两段 `k=3, [[1,1,1],[5,5,1]]` 得 1，`k = 10^9, [[1,10^9,10^6]]` 得 993000007（$10^{15} \bmod (10^9+7)$）。 +- n = $2 \times 10^5$、坐标到 $10^9$ 的乱序随机数据，`k` 取 1、12345、$10^7$、$10^9$，每个 `k` 跑 5 次，每次 0.8 到 1.1 秒。同一台机器跑 `sum(range(10**7))` 要 0.2 秒，可以拿来估算换到别的机器上的时间。 ## 复杂度 -时间复杂度是 O(n log n)，来自一次排序和 2n 次二分查找。空间复杂度是 O(n)，用来存前缀和与两个端点列表。在本机实测，n = 2×10^5 时 Python 版大约 0.7 秒跑完。 +时间 $O(n \log n)$，来自一次排序和 2n 次二分。空间 $O(n)$，存前缀和与两个端点列表。 + +排序要写 `key=lambda seg: seg[0]`。不写 `key` 时，`sorted` 比较的是整个 `[l, r, money]` 列表，每次比较都要逐个元素去比，同一组 $2 \times 10^5$ 的数据单排序就要 0.7 秒，加上 `key` 只要 0.2 秒。段互不相交，起点各不相同，所以只按起点排和按整行排结果一样。整段代码在同一组数据上从 1.3 到 1.7 秒降到 0.8 到 1.1 秒。 + +剩下的时间大致是排序 0.2 秒，建端点列表和前缀和 0.3 秒，只跑 2n 次二分的循环 0.4 秒。二分也可以省掉：左端对齐的窗口随 `i` 增大往右移，最后一个被盖住的段 `j` 也只往后走，所以可以用一个只前进的指针代替二分，排序后的扫描是 $O(n)$。这就是面经里说的双指针写法。在同一组数据上它只快 0 到 0.2 秒（`k = 10^9` 时反而略慢），所以这里用代码更短、更不容易写错的二分。 + +> [!say] I sort by start, build prefix sums of full segment totals, and for each of the 2n candidates I binary-search the segment where the window ends. Full segments come from the prefix sums, and the boundary segment only adds its covered part. That's O(n log n) time and O(n) space. Window sums can reach about 1e15, so I compare the true sums and apply the modulo once at the end. ## 易错点 -- **只检查「左端对齐段起点」的窗口是不够的**。例如 `[[1,10,1],[11,11,100]]`、`k = 3`：最优窗口是 [9–11]，金额 102，它的右端对齐的是第二段的终点；如果只看左端对齐的窗口，最多只能找到 100。 -- **取模一定放到最后**。在题目给的数据范围内就能构造出反例：`k = 1001`，`[[1,1001,10^6],[3001,4001,999000]]`。第一段整段的真实金额是 1,001,000,000，取模后变成 999993；第二段整段是 999,999,000，比模数小，取模后不变。正确答案是 999993；但如果每个窗口先取模再比大小，就会错选 999999000。同样的道理，前缀和也不能边加边取模，否则两个前缀和相减、以及比较大小，结果都不对。 -- **被盖住一部分的段，长度和括号容易写错**。这部分的金额是 `(min(r_j, end) - l_j + 1) * c_j`（右端对齐时对应的是 `max(l_j, start)`），其中的 `+ 1`、该用 `min` 还是 `max`，以及整个括号，都容易出错。面经里提醒的「乘法优先级」指的就是这里：如果漏掉括号，写成 `... - l_j + 1 * c_j`，乘法只作用在 `1` 上，结果完全错误。可以用两种情况手动验证：`k = 1`，以及窗口恰好等于一整段。 -- **Java 要用 `long`，C++ 要用 `long long`（或 `int64_t`）**。`(长度) * money` 最大是 10^9 × 10^6 = 10^15，前缀和也能到 10^15，用 int 一定会溢出（overflow）。C++ 不能用 `long` 代替，因为 `long` 的位数由编译器决定：Windows 上的 MSVC 编译器采用 LLP64 数据模型，`long` 只有 32 位，照样会溢出。乘法要先把一个因子转成 64 位再乘，Java 写成 `(long)(end - l + 1) * c`，C++ 写成 `(long long)(end - l + 1) * c` 或 `1LL * (end - l + 1) * c`；如果先用 int 乘完再转，溢出已经发生了。`l + k - 1` 最大约 2×10^9，刚好还在 int 的范围内，但也建议统一用 64 位整数。Python 的整数没有位数上限，不存在这个问题。 -- **输入不保证有序**。如果忘了先排序，`starts` 和 `ends` 就不是有序列表，二分查找的结果没有意义。 -- **`k` 很大时不需要特判**。`k` 比所有段的总跨度还大时，公式照样成立：二分会落到最后一段，整段金额都计入。 +下面三个错误写法都和正确版本在同一组输入上跑过（2026-10-27）： -## 测试用例 +| 错误写法 | 输入 | 正确版本 | 错误写法 | +| --- | --- | --- | --- | +| 只看左端对齐段起点的窗口 | 原帖样例 | 16 | 14 | +| 只看左端对齐段起点的窗口 | `k=3, [[1,10,1],[11,11,100]]` | 102 | 100 | +| 每个窗口先取模再比较 | `k=1001, [[1,1001,10^6],[3001,4001,999000]]` | 999993 | 999999000 | +| 部分段漏了括号 | `k=3, [[1,1,100],[2,10,5]]` | 110 | 106 | -下表的用例都实际跑过。其中 k=10^9 那一行的真实和是 10^15，没法逐个袋子暴力枚举，期望值是按公式算出的 10^15 mod (10^9+7)；其余各行的期望值都和逐个袋子枚举的暴力解对过。 +- **只看一个方向**。最优窗口可能只有右端贴着段终点，原因见「关键一步」最后一段。随机对拍的 2000 组里，只看左端的写法错了 104 组。 +- **取模放早了**。上表第三行，第一段整段真实金额是 1,001,000,000，取模后变成 999993。第二段整段 999,999,000 比模数小，取模后不变。先取模再比较就错选了第二段。前缀和也不能边加边取模，相减和比大小都会出错。 +- **被盖住一部分的段写错长度或括号**。面经提醒的「乘法优先级」就在这里：`(min(rj, win_end) - lj + 1) * mj` 漏掉括号写成 `min(rj, win_end) - lj + 1 * mj`，乘法只作用在 `1` 上。上表第四行，[1–3] 的正确金额是 100 + 2×5 = 110，漏括号算成 100 + 3 − 2 + 5 = 106。写完用 `k = 1` 和「窗口恰好等于一整段」两种情况手动验一遍。 -| 输入 | 期望 | 说明 | -| --- | --- | --- | -| `k=5, [[1,4,2],[6,6,5],[7,7,7],[9,10,1]]` | 16 | 原帖样例，取 3–7 号 | -| `k=1`，同上 | 7 | 只取一个袋子，答案是单袋最大值 | -| `k=100`，同上 | 22 | 窗口比所有段的总跨度还大，全部拿到 | -| `k=3, [[7,7,7],[1,4,2],[9,10,1],[6,6,5]]` | 12 | 输入乱序；最优窗口是 [5–7] 或 [6–8] | -| `k=3, [[1,10,1],[11,11,100]]` | 102 | 只有右端对齐的窗口才能找到最优解 | -| `k=3, [[1,1,100],[2,10,1]]` | 102 | 最优窗口是左端对齐的 | -| `k=3, [[1,1,1],[5,5,1]]` | 1 | 窗口长度不够同时盖住两段 | -| `k=4, [[1,2,3],[3,4,5]]` | 16 | 两段相邻，中间没有空袋子 | -| `k=10^9, [[1,10^9,10^6]]` | 993000007 | 真实和是 10^15，期望值是取模后的结果 | -| `k=1001, [[1,1001,10^6],[3001,4001,999000]]` | 999993 | 如果先取模再比较，会错得到 999999000 | -| `k=4, [[1,3,2],[5,6,4],[8,10,1]]` | 10 | （站方 AI 整理，未经原帖证实）最优窗口是 [3–6]，和暴力解验算一致 | - -随机小数据上的对拍一共跑了 2000 组：n 取 1 到 6，坐标最大到 40，k 取 1 到 45，金额取 1 到 10，数据里包含只含一个袋子的段、相邻的段和乱序输入。每一组都和两种暴力解比过（分别按 OA 的「从 1 号开始」和 LeetCode 的「整条数轴」理解），结果全部一致。大数据测试用的是 n = 2×10^5、坐标到 10^9，k 分别取 1、12345、10^7、10^9，二分版和下面 Follow-up 里的双指针版答案一致。 - -## Follow-up - -**双指针写法，排序之后只要 O(n)**。这是面经里提到的另一种做法。左端对齐段起点的窗口，随着 `i` 增大只会往右移，窗口右端 `end` 也只增不减，所以「完整落在窗口里的段到哪一段为止」也只会往后走。用一个指针 `j` 记录这个位置，它只前进、不后退，所以在整个循环里最多移动 n 次，排好序以后扫一遍就是 O(n)，不需要每次都二分。右端对齐的情况不用另写一套：把每段的坐标镜像成 `(-r, -l, c)`，相当于把数轴左右翻转，原来「右端对齐某段终点」的窗口就变成了「左端对齐某段起点」，再调用同一个函数即可。这段代码已运行，和上面的二分版对拍结果一致： - -```python -MOD = 10**9 + 7 - - -def _best_left_aligned(segs, k): - """segs 按起点升序；只看左端对齐某段起点的窗口 [l_i, l_i + k - 1]。""" - n = len(segs) - best = 0 - full = 0 # 段 i..j-1 都完整落在窗口里，它们的金额和 - j = 0 - for i, (l, r, c) in enumerate(segs): - if j < i: # 上一轮连第 i-1 段都没装满，重新从第 i 段数 - j, full = i, 0 - end = l + k - 1 - while j < n and segs[j][1] <= end: - full += (segs[j][1] - segs[j][0] + 1) * segs[j][2] - j += 1 - part = 0 - if j < n and segs[j][0] <= end: # 第 j 段只盖住前半截 - part = (end - segs[j][0] + 1) * segs[j][2] - best = max(best, full + part) - if j > i: # 左端要挪到下一段，扣掉第 i 段 - full -= (r - l + 1) * c - return best - - -def calculateMaximumConsecutiveSum(k, segment): - segs = sorted(segment) - mirrored = sorted((-r, -l, c) for l, r, c in segment) # 镜像后，右端对齐变成左端对齐 - return max(_best_left_aligned(segs, k), _best_left_aligned(mirrored, k)) % MOD -``` - -**不加权的版本是 LeetCode 2271 Maximum White Tiles Covered by a Carpet**。那道题是用一块固定长度的地毯盖住尽量多的白色瓷砖（white tile），相当于本题里每段的金额都相同。由于每块瓷砖的价值一样，窗口两端都有瓷砖时，左移一格的变化量是 0，所以只看「左端对齐段起点」的窗口就够了。本题是带权的，每段金额不同，两个方向都必须看。 - -**如果段可以重叠，重叠位置的金额要叠加**。这时可以用差分（difference）的思路，只记录金额在哪些位置发生变化：每段在起点处记一个「金额增加 money」的变化点，在终点的下一个位置记一个「金额减少 money」的变化点。坐标很大，不能真的开一个按坐标下标的数组，所以把这些变化点按坐标排序，再用扫描线（sweep line）从左到右扫一遍、累加变化量。相邻两个变化点之间的金额不变，正好是一个小段，这样就把所有段切成了互不相交的小段。切好以后，再套用上面的解法【推断】，未运行。 - -**如果题目改成「至多取 k 个」**，答案不变：金额都是非负的，取满 k 个不会比少取更差。 - -## 英文讲法 - -> [!say] The money is piecewise constant over disjoint segments, and both coordinates and k go up to 1e9, so I can't expand the bags one by one. The key observation is that some optimal window either starts exactly at a segment's start or ends exactly at a segment's end. If neither edge is on a boundary, sliding the window one step right or one step left changes the sum by opposite amounts, so one direction never hurts, and I keep sliding until I hit a boundary. That leaves only 2n candidate windows. - -> [!say] I sort the segments by start and build prefix sums of the full segment totals. For each candidate I binary-search the last segment the window reaches. Segments fully inside come from the prefix sum, and the boundary segment only contributes the part that's covered. That's O(n log n) time and O(n) space. Window sums can reach about 1e15, so I compare the true sums (64-bit in Java) and apply the modulo only once, at the very end. +> [!optional] Java 和 C++ 里，一段的金额最大是 $10^9 \times 10^6 = 10^{15}$，前缀和也能到这个量级，要用 `long`（Java）或 `long long`（C++）。C++ 不要用 `long`，Windows 上的 MSVC 采用 LLP64 数据模型，`long` 只有 32 位。乘法要先把一个因子转成 64 位再乘，Java 写成 `(long)(win_end - lj + 1) * mj`，C++ 写成 `1LL * (win_end - lj + 1) * mj`，先用 int 乘完再转，溢出已经发生了。Python 的整数没有位数上限，没有这个问题。
meta
@@ -3,4 +3,7 @@ "lc_freq": 96, "premium": false, - "neetcode150": false + "neetcode150": false, + "depth_guide": "2026-10-23", + "rewritten_by": "cloud:20261026-2313", + "rewritten_at": "2026-10-27" }