Medium

题目描述

给你一个长度为 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^5
  • 1 <= weight[i] <= 10^9

提示:

  • 使用单调栈为每个结束索引 i 找到最近的前一个索引 j，满足 weight[j] > weight[i]（如果没有则设 j = -1）。
  • 然后设置 dp[i] = best[j] + 1（使用 best[-1] = 0），并更新 best[i] = max(best[i-1], dp[i])；结果是 best[n-1]。

解题思路

解题思路

这道题需要我们找到最多的不重叠平衡货运。平衡货运的关键条件是：最后一个包裹的重量严格小于货运中的最大重量。

核心观察

  1. 对于以位置 i 结尾的货运，要使其平衡，我们需要在 i 之前找到一个位置 j，使得 weight[j] > weight[i]
  2. 这样从 j 到 i 的子数组就是一个平衡货运，因为最大值是 weight[j]，最后值是 weight[i]

算法设计

使用动态规划 + 单调栈的方法：

  1. 单调栈预处理：对每个位置 i，找到最近的左边位置 j 使得 weight[j] > weight[i]
  2. 动态规划：
    • dp[i] 表示以位置 i 结尾的货运能达到的最大平衡货运数
    • best[i] 表示前 i 个位置能达到的最大平衡货运数
    • 状态转移：dp[i] = best[j] + 1（j 是找到的左边较大元素位置）
    • best[i] = max(best[i-1], dp[i])

时间复杂度分析

  • 单调栈：O(n)
  • 动态规划：O(n)
  • 总时间复杂度：O(n)

这个方法巧妙地利用了单调栈快速找到左边第一个更大元素的特性，结合动态规划实现最优解。

代码实现

class Solution {
public:
    int maxBalancedShipments(vector<int>& weight) {
        int n = weight.size();
        vector<int> leftGreater(n, -1);
        stack<int> st;
        
        // 使用单调栈找到每个位置左边第一个更大的元素
        for (int i = 0; i < n; i++) {
            while (!st.empty() && weight[st.top()] <= weight[i]) {
                st.pop();
            }
            if (!st.empty()) {
                leftGreater[i] = st.top();
            }
            st.push(i);
        }
        
        // 动态规划
        vector<int> dp(n, 0);
        vector<int> best(n, 0);
        
        for (int i = 0; i < n; i++) {
            if (leftGreater[i] != -1) {
                int j = leftGreater[i];
                dp[i] = (j == 0 ? 0 : best[j - 1]) + 1;
            }
            best[i] = (i == 0 ? 0 : best[i - 1]);
            best[i] = max(best[i], dp[i]);
        }
        
        return best[n - 1];
    }
};

class Solution:
    def maxBalancedShipments(self, weight: List[int]) -> int:
        n = len(weight)
        leftGreater = [-1] * n
        stack = []
        
        # 使用单调栈找到每个位置左边第一个更大的元素
        for i in range(n):
            while stack and weight[stack[-1]] <= weight[i]:
                stack.pop()
            if stack:
                leftGreater[i] = stack[-1]
            stack.append(i)
        
        # 动态规划
        dp = [0] * n
        best = [0] * n
        
        for i in range(n):
            if leftGreater[i] != -1:
                j = leftGreater[i]
                dp[i] = (0 if j == 0 else best[j - 1]) + 1
            best[i] = 0 if i == 0 else best[i - 1]
            best[i] = max(best[i], dp[i])
        
        return best[n - 1]

public class Solution {
    public int MaxBalancedShipments(int[] weight) {
        int n = weight.Length;
        int[] leftGreater = new int[n];
        Array.Fill(leftGreater, -1);
        Stack<int> stack = new Stack<int>();
        
        // 使用单调栈找到每个位置左边第一个更大的元素
        for (int i = 0; i < n; i++) {
            while (stack.Count > 0 && weight[stack.Peek()] <= weight[i]) {
                stack.Pop();
            }
            if (stack.Count > 0) {
                leftGreater[i] = stack.Peek();
            }
            stack.Push(i);
        }
        
        // 动态规划
        int[] dp = new int[n];
        int[] best = new int[n];
        
        for (int i = 0; i < n; i++) {
            if (leftGreater[i] != -1) {
                int j = leftGreater[i];
                dp[i] = (j == 0 ? 0 : best[j - 1]) + 1;
            }
            best[i] = i == 0 ? 0 : best[i - 1];
            best[i] = Math.Max(best[i], dp[i]);
        }
        
        return best[n - 1];
    }
}

/**
 * @param {number[]} weight
 * @return {number}
 */
var maxBalancedShipments = function(weight) {
    const n = weight.length;
    let count = 0;
    let i = 0;
    
    while (i < n) {
        let maxWeight = weight[i];
        let found = false;
        
        for (let j = i + 1; j < n; j++) {
            maxWeight = Math.max(maxWeight, weight[j]);
            if (weight[j] < maxWeight) {
                count++;
                i = j + 1;
                found = true;
                break;
            }
        }
        
        if (!found) {
            i++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)单调栈遍历一次数组为O(n)，动态规划遍历一次数组为O(n)
空间复杂度O(n)需要额外的数组存储leftGreater、dp、best信息，以及单调栈的空间