2026-01-09：平衡装运的最大数量。用go语言，给定一个长度为 n 的整数数组 weight，表示沿一条直线排列的 n 个包裹的重量。把若干个相邻

福大大架构师每日一题

发布于 2026-01-12 11:10:59

750

2026-01-09：平衡装运的最大数量。用go语言，给定一个长度为 n 的整数数组 weight，表示沿一条直线排列的 n 个包裹的重量。把若干个相邻的包裹作为一次“装运”（即数组中的一个连续区间）。当某次装运中最右端的包裹重量严格小于该区间内出现的最大重量时，称这次装运为“平衡装运”（即区间的最后一个元素不是该区间的最大值）。

现在要从数组中挑出若干个互不重叠的平衡装运，使得每个包裹最多被选入一次（允许有包裹不被任何装运包含）。求可以选出的平衡装运的最大数量。

2 <= n <= 100000。

1 <= weight[i] <= 1000000000。

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

输出: 2。

解释:

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

装运 1: [2, 5, 1]

包裹的最大重量 = 5

最后一个包裹的重量 = 1，严格小于 5，因此这是平衡装运。

装运 2: [4, 3]

包裹的最大重量 = 4

最后一个包裹的重量 = 3，严格小于 4，因此这是平衡装运。

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

题目来自力扣3638。

解决思路分步描述

第1步：理解问题核心 目标是找到最多的互不重叠的“平衡装运”区间。一个区间是“平衡”的，当且仅当该区间内最后一个包裹的重量严格小于该区间内的最大重量。这意味着，区间末尾的包裹不能是区间内最重的。最终需要返回的是这类区间的最大可能数量。

第2步：核心贪心策略 算法采用贪心算法，其核心思想是：尽可能早地、尽可能多地形成有效的平衡装运区间。具体来说，我们从左到右遍历包裹，一旦发现一个可能形成平衡装运的机会，就立即将其确定下来。这样做是因为如果一个平衡装运结束得越早，就越能为后面的包裹留下更多空间去形成新的、独立的平衡装运，从而有望增加总区间数量。

第3步：遍历与区间识别

1. 初始化：从数组的第二个包裹（索引为1）开始遍历。ans 计数器初始化为0，用于记录找到的平衡装运数量。
2. 寻找平衡点：对于当前遍历到的位置 i，我们检查其前一个包裹 weight[i-1] 和当前包裹 weight[i]。关键判断是：如果 weight[i-1] > weight[i]，那么以 i 为结尾、至少包含 i-1 和 i 两个包裹的区间，其末尾重量 weight[i] 已经严格小于区间内的某个重量（至少是 weight[i-1]）。这恰好满足了平衡装运的条件。
3. 立即划分：一旦上述条件成立，算法就认为找到了一个有效的平衡装运。于是：
- • 将计数器 ans 加1。
- • 执行 i++。这一步非常关键，它意味着我们将当前平衡装运的结束位置固定在 i，并且跳过下一个包裹（即索引 i+1）。这是因为我们刚刚确定的区间已经占用了包裹 i-1 和 i。跳过下一个包裹是为了确保各个平衡装运区间互不重叠，并且为寻找下一个区间留出空间。下一次循环将从 i+2 开始检查。

第4步：处理未满足条件的情况 如果在位置 i 不满足 weight[i-1] > weight[i] 的条件，说明以 i 结尾的、包含前一个包裹的短区间无法构成平衡装运。此时，算法不做任何操作，只是简单地将 i 加1，继续检查下一个位置，期待在后续的遍历中找到满足条件的区间。

第5步：遍历完成 当遍历完整个数组后，计数器 ans 的值就是采用此贪心策略能找到的互不重叠的平衡装运的最大数量。

复杂度分析

• 总的时间复杂度：O(n)。算法主要操作是一次从左到右的线性遍历。在遍历过程中，每个包裹最多被访问一次。虽然存在 i++ 的跳步操作，但这只是减少了总循环次数，并没有在任何一个包裹上执行重复或复杂的操作（如回溯、嵌套循环）。因此，时间复杂度是线性的。
• 总的额外空间复杂度：O(1)。算法只使用了固定数量的额外变量，如循环索引 i 和计数器 ans。这些变量的空间消耗与输入数组的大小 n 无关。它没有使用任何额外的、规模与 n 相关的数据结构（如栈、队列或动态规划数组）。因此，空间复杂度是常数级别的。

总结

这个解决方案的精髓在于其贪心策略：通过一次线性扫描，每当发现一个局部可行的平衡装运（即前一个包裹重量大于当前包裹）时，就立即确认它并跳过下一个包裹，从而高效地找出最大数量的不重叠区间。这种方法保证了高的效率，其时间复杂度和空间复杂度都非常理想。

Go完整代码如下：

package main

import (
    "fmt"
)

func maxBalancedShipments(weight []int) (ans int) {
    for i := 1; i < len(weight); i++ {
        if weight[i-1] > weight[i] {
            ans++
            i++ // 下个子数组至少要有两个数
        }
    }
    return
}

func main() {
    weight := []int{2, 5, 1, 4, 3}
    result := maxBalancedShipments(weight)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def maxBalancedShipments(weight):
    ans = 0
    i = 1
    n = len(weight)
    
    while i < n:
        if weight[i-1] > weight[i]:
            ans += 1
            i += 2  # 下个子数组至少要有两个数
        else:
            i += 1
            
    return ans

if __name__ == "__main__":
    weight = [2, 5, 1, 4, 3]
    result = maxBalancedShipments(weight)
    print(result)

C++完整代码如下：

#include <iostream>
#include <vector>

using namespace std;

int maxBalancedShipments(vector<int>& weight) {
    int ans = 0;
    int n = weight.size();

    for (int i = 1; i < n; i++) {
        if (weight[i - 1] > weight[i]) {
            ans++;
            i++; // 下个子数组至少要有两个数
        }
    }

    return ans;
}

int main() {
    vector<int> weight = {2, 5, 1, 4, 3};
    int result = maxBalancedShipments(weight);
    cout << result << endl;

    return0;
}