贪心
因为每次拆分要么长度等于1, 要么总和$\geq m$, 所以我们从两边一点一点向中间分离, 每次只分离出1个元素就可以达到最优解
判断这个问题的唯一指标就变成了
-
当$n \geq 3$ 是否存在两个相邻的元素的和$\geq m$, 因为在分离最后两个元素的上一步需要这两个元素和大于等于m
-
同时注意当$1 \leq n \leq 2$时是一定可以拆分的
时间复杂度 $O(n)$
Python代码
class Solution:
def canSplitArray(self, nums: List[int], m: int) -> bool:
if len(nums) <= 2: return True
for x, y in pairwise(nums):
if x + y >= m: return True
return False