解题思路
本题等价于:将数组划分为恰好 k 个连续非空段,使各段元素和的最大值最小。这是经典的 二分答案 + 贪心验证 问题(与 LeetCode 410「分割数组的最大值」同型)。
- 答案单调性:若最大段和 limit 可行,则任意更大的 limit 也可行;反之不可行时,更小的 limit 也不可行。因此在 [max(nums), ∑nums] 上二分。
- 可行性检验
can(limit):从左到右贪心累加,当前段和超过 limit 则开新段;统计所需最少段数 cnt。若 cnt <= k,说明可在不超过 limit 的前提下拆成至多 k 段;由于 k≤n 且每段非空,还可继续细分至恰好 k 段而不增大最大值。
- 二分得到最小可行
limit 即为答案。
常见假解:用 DP 求最小段和(方向反了)、检验时用 cnt == k 而非 cnt <= k、忘记单元素下界 max(nums)。