跳转至

3638. 平衡装运的最大数量

题目描述

给你一个长度为 n 的整数数组 weight，表示按直线排列的 n 个包裹的重量。装运 定义为包裹的一个连续子数组。如果一个装运满足以下条件，则称其为 平衡装运：最后一个包裹的重量 严格小于 该装运中所有包裹中 最大重量 。

选择若干个 不重叠 的连续平衡装运，并满足 每个包裹最多出现在一次装运中（部分包裹可以不被装运）。

返回 可以形成的平衡装运的最大数量 。

 

示例 1:

输入: weight = [2,5,1,4,3]

输出: 2

解释:

我们可以形成最多两个平衡装运：

  • 装运 1: [2, 5, 1]
    • 包裹的最大重量 = 5
    • 最后一个包裹的重量 = 1，严格小于 5，因此这是平衡装运。
  • 装运 2: [4, 3]
    • 包裹的最大重量 = 4
    • 最后一个包裹的重量 = 3，严格小于 4，因此这是平衡装运。

无法通过其他方式划分包裹获得超过两个平衡装运，因此答案是 2。

示例 2:

输入: weight = [4,4]

输出: 0

解释:

在这种情况下无法形成平衡装运：

  • 装运 [4, 4] 的最大重量为 4，而最后一个包裹的重量也是 4，不严格小于最大重量，因此不是平衡的。
  • 单个包裹的装运 [4] 中，最后一个包裹的重量等于最大重量，因此也不是平衡的。

由于无法形成任何平衡装运，答案是 0。

 

提示:

  • 2 <= n <= 105
  • 1 <= weight[i] <= 109

解法

方法一：贪心

我们维护当前遍历的数组的最大值 \(\text{mx}\)，并遍历数组中的每个元素 \(x\)。如果 \(x < \text{mx}\)，则说明当前元素可以作为一个平衡装运的最后一个包裹，因此我们就将答案加一，并将 \(\text{mx}\) 重置为 0。否则，我们更新 \(\text{mx}\) 为当前元素 \(x\) 的值。

遍历结束后，返回答案即可。

时间复杂度 \(O(n)\)，其中 \(n\) 是数组的长度。空间复杂度 \(O(1)\)，只使用了常数级别的额外空间。

1
2
3
4
5
6
7
8
9
class Solution:
    def maxBalancedShipments(self, weight: List[int]) -> int:
        ans = mx = 0
        for x in weight:
            mx = max(mx, x)
            if x < mx:
                ans += 1
                mx = 0
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int maxBalancedShipments(int[] weight) {
        int ans = 0;
        int mx = 0;
        for (int x : weight) {
            mx = Math.max(mx, x);
            if (x < mx) {
                ++ans;
                mx = 0;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int maxBalancedShipments(vector<int>& weight) {
        int ans = 0;
        int mx = 0;
        for (int x : weight) {
            mx = max(mx, x);
            if (x < mx) {
                ++ans;
                mx = 0;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func maxBalancedShipments(weight []int) (ans int) {
    mx := 0
    for _, x := range weight {
        mx = max(mx, x)
        if x < mx {
            ans++
            mx = 0
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function maxBalancedShipments(weight: number[]): number {
    let [ans, mx] = [0, 0];
    for (const x of weight) {
        mx = Math.max(mx, x);
        if (x < mx) {
            ans++;
            mx = 0;
        }
    }
    return ans;
}

评论