What is the pattern used to solve the Maximum Balanced Shipments problem?

The problem can be solved using a monotonic stack to identify valid subarrays and a greedy approach for optimal shipment partitioning.

How can I efficiently find valid shipments in the Maximum Balanced Shipments problem?

Using a monotonic stack to track indices allows you to efficiently find the nearest valid shipment end, helping you partition the array.

What is the time complexity of solving Maximum Balanced Shipments?

The time complexity is O(n), where n is the number of parcels, using a monotonic stack approach.

Can the Maximum Balanced Shipments problem be solved without a monotonic stack?

While a monotonic stack provides an efficient solution, the problem can also be solved with a brute-force approach, though it would not scale well with large inputs.

What are some edge cases to consider for Maximum Balanced Shipments?

Edge cases include arrays where all parcels are the same weight or arrays with only two parcels.

#3638

Medium

auto_awesomeMaximum Balanced Shipments core interview pattern

LeetCode 题解工作台

平衡装运的最大数量

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

题目描述

给你一个长度为 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 <= 10⁵
1 <= weight[i] <= 10⁹

lightbulb

解题思路

方法一：贪心

我们维护当前遍历的数组的最大值 $\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

10

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate uses a monotonic stack to efficiently find valid subarrays.
question_mark
The candidate demonstrates an understanding of greedy algorithms for partitioning.
question_mark
The candidate ensures no overlapping parcels in the selected shipments.

warning

常见陷阱

外企场景

error
Failing to account for parcels that are unshipped.
error
Not ensuring the shipment balance condition holds (last parcel being less than max weight).
error
Using an inefficient brute force approach, leading to time limit issues.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Variation 1: Handle edge cases like when there are only two parcels or when all parcels have the same weight.
arrow_right_alt
Variation 2: Modify the problem to allow a partial shipment, i.e., shipments that do not need to be contiguous.
arrow_right_alt
Variation 3: Change the weight constraint, making parcels weigh much more or less, affecting the balance condition.

help

常见问题

外企场景

探索更多题目 →

auto_awesome

继续模式

Maximum Balanced Shipments core interview pattern

用同一解题框架扩展到更多题目。

arrow_forward signal_cellular_alt

同难度题单

中等

按当前难度继续强化稳定输出。

arrow_forward