求环形列表删除所有元素的最大与最小操作次数

一、最大操作次数分析 #

要最大化操作次数，核心是尽可能避免触发自动删除，即每次删除元素后，左右相邻元素不相等。

规律总结 #

• 当所有元素都相同时：
  • 若列表长度 n == 1，操作次数为 1（直接删除唯一元素）。
  • 若 n > 1，操作次数为 2：删除任意一个元素后，剩余元素会自动删除至仅剩一个，再删除最后一个元素即可。
• 否则，最大操作次数为 n：可以通过每次选择删除左右元素不相等的位置，确保每次仅手动删除一个元素，无自动删除触发，最终需要 n 次操作。

二、最小操作次数分析 #

要最小化操作次数，核心是尽可能触发更多自动删除，即每次删除元素后，让系统自动删除尽可能多的相邻相等元素。

思路与规律 #

1. 特殊情况：所有元素相同
   同最大操作次数的特殊情况，操作次数为 1（n=1）或 2（n>1）。

2. 高频元素占比超过一半
   记出现次数最多的元素频率为 maxFreq，总元素数为 n。若 maxFreq > n/2，则最小操作次数为 2*maxFreq - n。

   • 解释：其他元素总共 n - maxFreq 个，每个可与一个高频元素配对，触发自动删除；剩余的 maxFreq - (n - maxFreq) 个高频元素无法通过自动删除消除，需手动删除。

3. 高频元素占比不超过一半
   这种情况需要结合列表的相邻关系判断，可通过动态规划求解：

   • 由于列表是环形，我们可以拆分为两种线性列表处理：去掉第一个元素的线性列表、去掉最后一个元素的线性列表。
   • 对每个线性列表，用动态规划计算最小操作次数：
     • 定义 dp[i][j] 表示删除线性列表中从索引 i 到 j 的所有元素所需的最小操作次数。
     • 状态转移：
       • 若 nums[i] == nums[j]，则 dp[i][j] = dp[i][j-1]（删除 j 时会触发自动删除 i 附近的相同元素，可合并操作）。
       • 否则，dp[i][j] = min(dp[i][k] + dp[k+1][j]) 对所有 k 属于 [i,j-1] 取最小值。
   • 最终环形列表的最小操作次数为两种线性情况的最小值。

   注：对于无相邻相等元素的环形列表（如 [1,2,3,4]），无法触发任何自动删除，最小操作次数为 n。

三、Java代码实现 #

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

public class CircularListDelete {

    // 计算最大操作次数
    public static int maxOperations(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        // 检查所有元素是否相同
        boolean allSame = true;
        int first = nums[0];
        for (int num : nums) {
            if (num != first) {
                allSame = false;
                break;
            }
        }
        if (allSame) {
            return n == 1 ? 1 : 2;
        } else {
            return n;
        }
    }

    // 计算最小操作次数
    public static int minOperations(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        // 检查所有元素是否相同
        boolean allSame = true;
        int first = nums[0];
        for (int num : nums) {
            if (num != first) {
                allSame = false;
                break;
            }
        }
        if (allSame) {
            return n == 1 ? 1 : 2;
        }

        // 统计最大频率
        Map<Integer, Integer> freqMap = new HashMap<>();
        int maxFreq = 0;
        for (int num : nums) {
            int freq = freqMap.getOrDefault(num, 0) + 1;
            freqMap.put(num, freq);
            maxFreq = Math.max(maxFreq, freq);
        }
        if (maxFreq > n / 2) {
            return 2 * maxFreq - n;
        }

        // 处理环形：拆分为两种线性情况
        int[] linear1 = new int[n - 1];
        System.arraycopy(nums, 1, linear1, 0, n - 1);
        int min1 = minLinearOperations(linear1);

        int[] linear2 = new int[n - 1];
        System.arraycopy(nums, 0, linear2, 0, n - 1);
        int min2 = minLinearOperations(linear2);

        return Math.min(min1, min2);
    }

    // 计算线性列表的最小操作次数（动态规划）
    private static int minLinearOperations(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        int[][] dp = new int[n][n];

        // 初始化：单个元素需要1次操作
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        // 填充dp表，长度从2到n
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len <= n; i++) {
                int j = i + len - 1;
                if (nums[i] == nums[j]) {
                    dp[i][j] = dp[i][j - 1];
                } else {
                    dp[i][j] = Integer.MAX_VALUE;
                    for (int k = i; k < j; k++) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                    }
                }
            }
        }
        return dp[0][n - 1];
    }

    public static void main(String[] args) {
        int[] example = {1, 2, 3, 2};
        System.out.println("最大操作次数：" + maxOperations(example)); // 输出4
        System.out.println("最小操作次数：" + minOperations(example)); // 输出3

        int[] allSame = {2, 2, 2};
        System.out.println("最大操作次数（全相同）：" + maxOperations(allSame)); // 输出2
        System.out.println("最小操作次数（全相同）：" + minOperations(allSame)); // 输出2

        int[] highFreq = {2, 2, 2, 1};
        System.out.println("最大操作次数（高频）：" + maxOperations(highFreq)); // 输出4
        System.out.println("最小操作次数（高频）：" + minOperations(highFreq)); // 输出2

        int[] alternating = {1, 2, 1, 2};
        System.out.println("最大操作次数（交替）：" + maxOperations(alternating)); // 输出4
        System.out.println("最小操作次数（交替）：" + minOperations(alternating)); // 输出3
    }
}

代码说明 #

• maxOperations 方法：通过检查所有元素是否相同，直接返回最大操作次数。
• minOperations 方法：先处理特殊情况，再判断高频元素占比，最后通过拆分环形为线性列表，调用动态规划方法求解。
• minLinearOperations 方法：使用动态规划计算线性列表的最小操作次数，处理元素相同和不同的情况。

内容的提问来源于stack exchange，提问作者Yu Xing