求解最大稳定集装箱段划分的正确高效算法（修复贪心解法错误）

嘿，我看了你这个问题，原来的贪心思路确实存在关键漏洞——它只想着尽可能多地分割段，却忽略了两个核心要求：所有集装箱必须被划分到合法的稳定段中，而且最后一段也必须满足稳定条件！你的测试用例失败就是因为代码分割出了很多段，但最后剩下的部分（比如那两个9）无法形成稳定段，导致整个划分无效，而正确的结果应该是只能把整个数组作为一个稳定段。

错误原因分析 #

原来的代码每次遇到当前元素小于当前段最大值就分割，但没有检查分割后剩余的部分是否能被合法划分。比如在那个失败的测试用例中，分割后的剩余部分最后元素是9，而剩余部分的最大值也是9，无法形成稳定段，这样的分割是无效的。同时，代码重置max为0也有问题，应该重置为最小值来重新计算下一段的最大值。

正确思路与高效解法 #

我们需要一个兼顾贪心分割和剩余部分合法性检查的O(n)算法，具体步骤如下：

1. 预处理右最大值数组：从右往左遍历数组，记录每个位置到数组末尾的最大值（rightMax[i]表示从i到最后一个元素的最大值）。这一步是为了快速判断任意位置之后的剩余部分是否能被合法划分。
2. 全局合法性检查：首先判断整个数组是否能被划分——只有当数组最后一个元素小于全局最大值时，才存在合法划分（否则任何包含最后一个元素的段都不稳定）。如果不满足，直接返回0。
3. 贪心遍历分割：从左到右遍历数组，维护当前段的最大值。对于每个位置，检查两个条件：
   • 当前段是稳定的（当前元素小于当前段的最大值）；
   • 分割后剩余的部分可以被合法划分（如果剩余部分为空则自动满足，否则剩余部分的最后元素必须小于剩余部分的最大值，也就是massList[n-1] < rightMax[i+1]）。
     当两个条件都满足时，我们在这里分割，计数加1，并重置当前段的最大值。
4. 最后一段的处理：遍历到最后一个元素时，剩余部分为空，只要当前段是稳定的，就计入计数。

完整Java代码 #

import java.util.*;

class ContainerPlanner {
    public static int getMaxStableSegments(List<Integer> massList) {
        int n = massList.size();
        if (n == 0) return 0;

        // 预处理右最大值数组，rightMax[i]表示从i到n-1的最大值
        long[] rightMax = new long[n + 1];
        rightMax[n] = Long.MIN_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            rightMax[i] = Math.max(massList.get(i), rightMax[i + 1]);
        }

        // 全局检查：整个数组是否存在合法划分的可能
        long lastMass = massList.get(n - 1);
        if (lastMass >= rightMax[0]) {
            return 0;
        }

        int stableCount = 0;
        long currentMax = Long.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            long currentMass = massList.get(i);
            currentMax = Math.max(currentMax, currentMass);

            // 检查当前段是否稳定
            boolean isCurrentStable = currentMass < currentMax;
            // 检查剩余部分是否可以被划分
            boolean canRestBePartitioned = (i == n - 1) 
                ? true 
                : (lastMass < rightMax[i + 1]);

            if (isCurrentStable && canRestBePartitioned) {
                stableCount++;
                currentMax = Long.MIN_VALUE; // 重置当前段最大值，准备下一段
            }
        }

        return stableCount;
    }

    public static void main(String[] args) {
        System.out.println(getMaxStableSegments(Arrays.asList(1, 2, 3, 2, 6, 3))); // 输出: 2
        System.out.println(getMaxStableSegments(Arrays.asList(8, 5, 4, 7, 2))); // 输出: 2
        System.out.println(getMaxStableSegments(Arrays.asList(4, 3, 6, 5, 3, 4, 7, 1))); // 输出: 3
        System.out.println(getMaxStableSegments(Arrays.asList(10, 5, 6, 4, 7, 6, 4, 2, 7, 1, 4, 6, 3, 4, 5, 1, 7, 5, 4, 6, 7, 8, 4, 6, 1, 9, 9))); // 输出: 1
    }
}

代码关键点说明 #

• 使用long类型：避免因为massList元素达到1e9导致的整数溢出问题。
• 右最大值数组：O(n)时间预处理，让我们可以O(1)判断剩余部分的合法性。
• 贪心分割的条件：确保每次分割后，剩余部分至少能形成一个稳定段（或者可以继续分割），这样就能保证整个划分的合法性。

内容来源于stack exchange