本文详解如何在满足“相邻相同元素自动消失”约束下，最大化两个篮子的总容量；重点剖析原始贪心策略的逻辑缺陷，并给出修正后的完整实现与原理分析。
本文详解如何在满足“相邻相同元素自动消失”约束下，最大化两个篮子的总容量；重点剖析原始贪心策略的逻辑缺陷，并给出修正后的完整实现与原理分析。
在题目设定中，我们有两个初始为空的篮子（可视为栈式结构），需按顺序将数组 A 的每个元素放入其中一个篮子。关键规则是：若某篮子末尾已有与当前元素相同的值，则该元素放入后会触发“魔法消失”——即新放入的元素立即被移除（而非保留并覆盖）。注意：消失仅发生在放入后检测到连续相等，且只移除后加入的那个元素（即“新元素自动消失”，原末尾元素仍保留）。
原始代码的根本错误在于：它仅做了“条件性添加”，却完全忽略了“添加后触发消失”的后果。例如，当 basket1 = [3]，当前 num = 3 时，代码判断 basket1.get(-1) == num 成立，于是尝试放入 basket2；但如果 basket2 为空或末尾非 3，就直接 add(3) —— 这看似规避了 basket1 的冲突，但遗漏了关键场景：若 basket2 末尾恰好也是 3，此时放入会导致 basket2 出现 [..., 3, 3]，从而触发新元素 3 自动消失，实际篮子大小并未增加。而原代码未做此校验，错误地计入了该次添加。
更严重的是，原始逻辑未覆盖“两篮均不可安全添加”的情形。例如 basket1 = [5], basket2 = [5]，当前 num = 5：无论放入哪个篮子，都会因末尾相同导致新元素立即消失。此时最优策略是跳过添加（即不放入任何篮子），而非强行塞入——因为强行添加只会白费一次操作，不增加总尺寸。
✅ 正确解法应基于贪心+状态模拟，每步决策需预判添加后的净效果：
- 若 num 与 basket1 末尾不同 → 放入 basket1 后尺寸 +1；
- 若 num 与 basket2 末尾不同 → 放入 basket2 后尺寸 +1；
- 若两者都可放，优先选其一（顺序不影响最优性）；
- 若两者末尾均等于 num → 当前元素无法增加任一篮子尺寸，跳过（不添加）。
以下是修正后的 Java 实现：
public static int maxBasketSum(int[] A) {
if (A == null || A.length == 0) return 0;
List<Integer> basket1 = new ArrayList<>();
List<Integer> basket2 = new ArrayList<>();
for (int num : A) {
boolean canAddTo1 = basket1.isEmpty() || basket1.get(basket1.size() - 1) != num;
boolean canAddTo2 = basket2.isEmpty() || basket2.get(basket2.size() - 1) != num;
if (canAddTo1 && canAddTo2) {
// 两者均可，任选其一（如优先 basket1）
basket1.add(num);
} else if (canAddTo1) {
basket1.add(num);
} else if (canAddTo2) {
basket2.add(num);
}
// 若 both false：跳过，不添加（无操作）
}
return basket1.size() + basket2.size();
}⚠️ 关键注意事项：
- “消失”不是删除旧元素，而是拒绝新元素落库：因此无需调用 remove()，只需控制 add() 的执行时机；
- 篮子行为本质是“栈顶匹配”，用 List.get(size-1) 模拟栈顶高效且准确；
- 时间复杂度为 O(N)，空间复杂度 O(N)，符合大规模输入要求；
- 该贪心策略已被证明最优：因每步决策仅依赖当前状态与局部约束，无后效性，且跳过无效添加不会损害后续机会。
总结：解决此类“带副作用的放置问题”，核心在于显式建模操作的净收益，而非仅规避表面冲突。务必区分“能否放入”和“放入后是否有效”，后者才是影响目标函数（总尺寸）的决定因素。
