给你一个长度为 n
的整数数组 weight
,表示按直线排列的 n
个包裹的重量。装运 定义为包裹的一个连续子数组。如果一个装运满足以下条件,则称其为 平衡装运:最后一个包裹的重量 严格小于 该装运中所有包裹中 最大重量 。
选择若干个 不重叠 的连续平衡装运,并满足 每个包裹最多出现在一次装运中(部分包裹可以不被装运)。
返回 可以形成的平衡装运的最大数量 。
示例 1:
输入: weight = [2,5,1,4,3]
输出: 2
解释:
我们可以形成最多两个平衡装运:
[2, 5, 1]
[4, 3]
无法通过其他方式划分包裹获得超过两个平衡装运,因此答案是 2。
示例 2:
输入: weight = [4,4]
输出: 0
解释:
在这种情况下无法形成平衡装运:
[4, 4]
的最大重量为 4,而最后一个包裹的重量也是 4,不严格小于最大重量,因此不是平衡的。[4]
中,最后一个包裹的重量等于最大重量,因此也不是平衡的。由于无法形成任何平衡装运,答案是 0。
提示:
2 <= n <= 105
1 <= weight[i] <= 109