本文讲解如何在满足“相邻相同元素自动消失”约束下，将数组元素最优分配至两个篮子，最大化最终总元素数；重点剖析原始贪心逻辑缺陷，并给出修正后的完整实现与原理分析。
本文讲解如何在满足“相邻相同元素自动消失”约束下，将数组元素最优分配至两个篮子，最大化最终总元素数；重点剖析原始贪心逻辑缺陷，并给出修正后的完整实现与原理分析。
在题目设定中，我们有两个初始为空的篮子（可视为栈式结构），需按顺序将数组 A 的每个元素放入其中一个篮子。关键规则是：若某篮子末尾已有元素 x，且新放入的仍是 x，则该次放入会导致「前一个 x 自动消失」——注意，这不是简单拒绝插入，而是「插入后立即触发前驱元素删除」，即：[..., x] + x → [...]（长度不变，但末尾 x 被抵消）。
原始代码的根本错误在于：它仅用 if-else 判断是否“允许添加”，却完全忽略了规则中的副作用删除机制。例如，当 basket1 = [3]，当前元素为 3 时，代码跳过 basket1、尝试放入 basket2；但如果 basket2 末尾也是 3，代码直接跳过（不添加），导致该元素彻底丢失——而题目要求必须放置（“place all elements sequentially”）。更严重的是，即使成功放入 basket2，若其末尾原为 3，则放入后应触发前一个 3 消失，但代码未执行任何删除操作。
✅ 正确建模方式：
每个篮子应维护实际存储状态，并在每次插入后显式检查并清理连续重复。由于只涉及末尾比较，只需检查 size() >= 1 && last == current，满足则 remove(size()-1)。
以下是修正后的 Java 实现：
public static int maxBasketSum(int[] A) {
List<Integer> basket1 = new ArrayList<>();
List<Integer> basket2 = new ArrayList<>();
for (int num : A) {
// 尝试放入 basket1：若末尾不冲突，直接加；若冲突，则加后删前一个
if (basket1.isEmpty() || basket1.get(basket1.size() - 1) != num) {
basket1.add(num);
} else {
// 冲突：先加，再删前一个（等价于抵消）
basket1.add(num);
basket1.remove(basket1.size() - 2); // 删除原末尾元素
}
// 同理处理 basket2：但注意——我们必须**选择使总长度最大的方案**
// 因此需比较两种选择：放b1 vs 放b2，取总size更大者
// → 原始单路径贪心失效！需动态规划或回溯？不，观察发现：
// 实际上，最优策略是：对每个元素，**优先放入不会引发删除的篮子；
// 若两边都会删除，则任选其一（效果相同）；若仅一边会删，则选不删的那边**
// 但等等——上述“先加后删”逻辑已隐含处理。真正问题在于：
// 我们不能独立决定每步放哪边，因为选择影响后续状态。
// 然而本题存在贪心性质：始终优先放入「当前不会导致删除」的篮子；
// 若两边都可放（都不删），任选；若仅一边可放，选之；若两边都删，则放哪边等价（均净增0）。
}
// ✅ 终极正确解法（O(n) 贪心）：
// 维护两篮子末尾元素（而非整个列表），因中间元素不影响未来决策
int tail1 = -1, tail2 = -1; // -1 表示空
int size1 = 0, size2 = 0;
for (int num : A) {
if (tail1 != num && tail2 != num) {
// 两边都不冲突 → 选较小size的篮子（平衡放置，为后续留余地）
if (size1 <= size2) {
tail1 = num;
size1++;
} else {
tail2 = num;
size2++;
}
} else if (tail1 != num) {
// 只有 basket1 可放
tail1 = num;
size1++;
} else if (tail2 != num) {
// 只有 basket2 可放
tail2 = num;
size2++;
}
// 若 tail1 == tail2 == num → 两边放都会删，净增0，跳过（元素被“吸收”但不增加长度）
}
return size1 + size2;
}⚠️ 关键注意事项：
- 不可维护完整列表：题目仅关心最终大小，且状态转移只依赖末尾元素，用 O(1) 空间维护 tail1/tail2 和 size1/size2 即可；
- “两边都冲突”时无需操作：此时无论放入哪个篮子，都会触发删除，净长度不变（+1−1=0），故跳过；
- 避免盲目“先加后删”模拟：虽逻辑正确，但易引发 IndexOutOfBoundsException 或冗余操作，状态抽象更鲁棒；
- 测试用例验证：A = [1,1,1] → 输出 2（如 b1=[1], b2=[1]，第三个 1 两边都冲突，不增加）；A = [1,2,1] → 输出 3（可实现 b1=[1,2], b2=[1]）。
总结：本题本质是带状态约束的在线分配问题。破题关键是准确解读“自动消失”的物理含义——它是插入的副作用，而非插入的前提条件。通过剥离无关细节、聚焦状态变量，即可将看似复杂的模拟转化为简洁高效的贪心算法。
