LeetCode-中等

1.2216 美化数组的最少删除数

1.题目描述

原题

2.思路

代码的主要思路是遍历数组，判断相邻元素是否相等，如果相等且满足删除条件，则删除一个元素。具体来说，代码中的 (i - cnt) % 2 == 0 表示当前位置 i 减去已删除元素的数目 cnt 后是否为偶数，这是为了保证删除操作只在偶数下标位置进行。然后通过 i + 1 < n 来判断是否已经遍历到数组的最后一个元素。如果相邻元素相等且满足删除条件，则将 cnt 自增 1，表示删除了一个元素。

最后，通过判断数组的长度是否为奇数来确定是否需要再删除一个元素。如果数组长度为奇数，则需要再删除一个元素，所以返回 cnt + 1；如果数组长度为偶数，则不需要再删除元素，直接返回 cnt

3.答案

public int minDeletion(int[] nums) {
    int n = nums.length; // 数组长度
    int cnt = 0; // 删除的元素数目

    for (int i = 0; i < n; i++) {
        if ((i - cnt) % 2 == 0 && i + 1 < n && nums[i] == nums[i + 1]) {
            cnt++; // 如果相邻元素相等且满足删除条件，则删除一个元素
        }
    }

    // 判断最后数组的长度是否为奇数，如果是奇数，则需要再删除一个元素
    return (n - cnt) % 2 != 0 ? cnt + 1 : cnt;
}

4.总结

这段代码使用了贪心思想（Greedy Approach）来解决问题。

贪心算法是一种在每个阶段选择局部最优解的策略，希望通过局部最优解的选择最终得到全局最优解。在这段代码中，贪心思想体现在删除相邻相等元素的过程中。每次遇到相邻相等的元素，就选择删除其中一个，以期望最终得到删除的元素数目最少的美丽数组。

具体来说，代码中的循环遍历数组，判断相邻元素是否相等，并满足删除条件。如果满足条件，就选择删除一个元素，以尽可能减少删除的次数。这种贪心的选择策略可以保证每次删除的都是相邻相等的元素，从而达到删除最少元素的目的。

贪心算法常常用于解决一些优化问题，其中每个阶段的选择都是局部最优的。然而，贪心算法并不保证能够得到全局最优解，因此在某些情况下可能会得到次优解或者不正确的结果。因此，在应用贪心算法时，需要仔细分析问题的特点，确保贪心策略的正确性。