特殊篮子放置数组元素求最大总容量：代码测试失败求修复

给定长度为N的整数数组A和两个空篮子，篮子有特殊特性：将元素放入篮子时，若篮子最后一个元素与当前元素相同，两者会抵消（即移除最后一个元素，当前元素不保留）；若不同则正常添加元素。需按顺序将A的所有元素放入任意一个篮子，求两个篮子的容量（元素数量）之和的最大值。

用户提供的代码如下，但大部分测试用例失败：

public static int countDistinctPairs(int[] A) {
    ArrayList<Integer> basket1 = new ArrayList<>();
    ArrayList<Integer> basket2 = new ArrayList<>();

    for (int num : A) {
        if (basket1.size() != 0 && basket1.get(basket1.size()-1) == num) {
            if (basket2.size() == 0 ||(basket2.size()!=0 && basket2.get(basket2.size()-1) !=num)) {
                basket2.add(num);
            }
        } else {
            basket1.add(num);
        }
    }

    return basket1.size() + basket2.size();
}

代码错误分析 #

1. 未强制放入所有元素：当两个篮子的最后元素都等于当前元素时，代码直接跳过该元素，违反题目“必须放入所有元素”的要求。
2. 错误处理抵消逻辑：放入元素时仅在篮子最后元素不同时才添加，未模拟“放入后抵消”的规则——即使篮子最后元素与当前元素相同，也必须放入并执行抵消操作，而非跳过。
3. 贪心策略片面：只优先往basket1放元素，未考虑放入basket2可能带来的后续更大收益，无法覆盖所有最优解场景。

正确解法思路 #

我们需要模拟每个元素放入两个篮子的所有可能状态，通过动态规划记录所有可行状态的最大总容量：

• 用HashMap存储当前所有状态：键为两个篮子的栈状态字符串（如"1,2|3"表示篮子1栈为[1,2]，篮子2栈为[3]），值为该状态的总容量。
• 初始状态为两个空篮子，总容量0。
• 遍历每个元素，对当前每个状态分别尝试放入两个篮子，生成新状态并更新HashMap中对应状态的最大总容量。
• 遍历结束后，取HashMap中所有状态的最大总容量即为答案。

正确代码实现 #

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class BasketCapacity {
    public static int maxTotalCapacity(int[] A) {
        // 键：两个篮子的栈状态，格式为 "basket1栈元素|basket2栈元素"，空栈用空字符串
        // 值：当前状态下的总容量
        Map<String, Integer> stateMap = new HashMap<>();
        stateMap.put("|", 0);

        for (int num : A) {
            Map<String, Integer> newStateMap = new HashMap<>();
            for (Map.Entry<String, Integer> entry : stateMap.entrySet()) {
                String stateKey = entry.getKey();
                int currentTotal = entry.getValue();
                String[] parts = stateKey.split("\\|");
                String b1Str = parts[0];
                String b2Str = parts[1];

                // 解析篮子1的栈
                Stack<Integer> b1Stack = new Stack<>();
                if (!b1Str.isEmpty()) {
                    for (String elem : b1Str.split(",")) {
                        b1Stack.push(Integer.parseInt(elem));
                    }
                }

                // 解析篮子2的栈
                Stack<Integer> b2Stack = new Stack<>();
                if (!b2Str.isEmpty()) {
                    for (String elem : b2Str.split(",")) {
                        b2Stack.push(Integer.parseInt(elem));
                    }
                }

                // 尝试放入篮子1
                Stack<Integer> newB1 = (Stack<Integer>) b1Stack.clone();
                if (newB1.isEmpty()) {
                    newB1.push(num);
                } else {
                    if (newB1.peek() == num) {
                        newB1.pop();
                    } else {
                        newB1.push(num);
                    }
                }
                String newB1Str = stackToString(newB1);
                String newStateKey1 = newB1Str + "|" + b2Str;
                int newTotal1 = newB1.size() + b2Stack.size();
                newStateMap.put(newStateKey1, Math.max(newStateMap.getOrDefault(newStateKey1, 0), newTotal1));

                // 尝试放入篮子2
                Stack<Integer> newB2 = (Stack<Integer>) b2Stack.clone();
                if (newB2.isEmpty()) {
                    newB2.push(num);
                } else {
                    if (newB2.peek() == num) {
                        newB2.pop();
                    } else {
                        newB2.push(num);
                    }
                }
                String newB2Str = stackToString(newB2);
                String newStateKey2 = b1Str + "|" + newB2Str;
                int newTotal2 = b1Stack.size() + newB2.size();
                newStateMap.put(newStateKey2, Math.max(newStateMap.getOrDefault(newStateKey2, 0), newTotal2));
            }
            stateMap = newStateMap;
        }

        // 找出所有状态中的最大总容量
        int maxTotal = 0;
        for (int total : stateMap.values()) {
            maxTotal = Math.max(maxTotal, total);
        }
        return maxTotal;
    }

    private static String stackToString(Stack<Integer> stack) {
        if (stack.isEmpty()) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < stack.size(); i++) {
            if (i > 0) {
                sb.append(",");
            }
            sb.append(stack.get(i));
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        // 测试用例1：[1,1,1]，预期结果1
        System.out.println(maxTotalCapacity(new int[]{1,1,1}));
        // 测试用例2：[1,2,1,2]，预期结果4
        System.out.println(maxTotalCapacity(new int[]{1,2,1,2}));
        // 测试用例3：[1,1,2,2]，预期结果4
        System.out.println(maxTotalCapacity(new int[]{1,1,2,2}));
    }
}

内容的提问来源于stack exchange，提问作者Nihal sharma