题目链接

小红的区间删除

题目描述

给定一个数组，小红可以执行最多一次操作：选择数组中两个值相等的元素，并将这两个元素之间的所有元素（不包括这两个元素本身）删除。

目标是计算出通过此操作最多可以删除多少个元素。

解题思路

题目的核心是找到一对值相等的元素，其在数组中的索引分别为 和 （假设 ），使得它们之间的元素数量 最大化。

为了最大化 对于一个特定的值，我们应该选择该值在数组中第一次出现的索引作为 ，以及最后一次出现的索引作为 。然而，一个更简洁的思路是，我们只需要记录每个元素第一次出现的索引。

我们可以使用一个哈希表（在 C++ 中是 std::map，Java 中是 HashMap，Python 中是 dict）来存储每个元素值首次出现的索引。

算法步骤如下：

  1. 初始化一个变量 为 0，用来记录最多可以删除的元素数量。

  2. 初始化一个哈希表 ，用于存储每个元素值第一次出现的索引。

  3. 从左到右遍历数组，对于当前索引为 的元素 ：

    • 检查 是否已经存在于 中。
    • 如果不存在，说明这是我们第一次遇到值为 的元素，我们将其索引存入哈希表：。
    • 如果 已经存在，说明我们之前已经在索引 处遇到过这个值的元素。这意味着我们找到了一个可以执行删除操作的区间。这个区间可以删除的元素数量为 。我们用这个值来更新 ：。

  4. 遍历完整个数组后， 的值就是最终的答案。如果数组中没有重复的元素，则无法执行操作，答案为 0。

这个方法只需一次遍历即可找到最优解，因为它对于每个重复出现的元素，都计算了它与第一次出现的那个元素之间的距离，并持续更新最大值。

代码

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> first_occurrence_map;
    int max_deleted_count = 0;

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (first_occurrence_map.count(a[i])) {
            max_deleted_count = max(max_deleted_count, i - first_occurrence_map[a[i]] - 1);
        } else {
            first_occurrence_map[a[i]] = i;
        }
    }

    cout << max_deleted_count << endl;

    return 0;
}

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        Map<Integer, Integer> firstOccurrenceMap = new HashMap<>();
        int maxDeletedCount = 0;

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            if (firstOccurrenceMap.containsKey(a[i])) {
                maxDeletedCount = Math.max(maxDeletedCount, i - firstOccurrenceMap.get(a[i]) - 1);
            } else {
                firstOccurrenceMap.put(a[i], i);
            }
        }

        System.out.println(maxDeletedCount);
    }
}

n = int(input())
a = list(map(int, input().split()))

first_occurrence_map = {}
max_deleted_count = 0

for i, val in enumerate(a):
    if val in first_occurrence_map:
        max_deleted_count = max(max_deleted_count, i - first_occurrence_map[val] - 1)
    else:
        first_occurrence_map[val] = i

print(max_deleted_count)

算法及复杂度

  • 算法：单次遍历 + 哈希表
  • 时间复杂度：在 C++ 中，使用 std::map 的时间复杂度为 ，其中 是数组的大小，因为每次对 std::map 的访问（插入或查找）需要 的时间，其中 是 map 中的元素数量 ()。在 Java 和 Python 中，使用 HashMap 和 dict 的平均时间复杂度为 。
  • 空间复杂度：，在最坏的情况下（数组中所有元素都不同），哈希表需要存储 个元素。