位置：首页-资讯-后端开发

java LeetCode刷题稍有难度的贪心构造算法

2023-02-03 12:01

短信预约 -IT技能 免费直播动态提醒

题目描述

这是 LeetCode 上的 768. 最多能完成排序的块 II ，难度为困难。

Tag : 「贪心」

这个问题和“最多能完成排序的块”相似，但给定数组中的元素可以重复，输入数组最大长度为 200020002000，其中的元素最大为 10810^8108。

arr 是一个可能包含重复元素的整数数组，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

我们最多能将数组分成多少块？

示例 1:

输入: arr = [5,4,3,2,1]
输出: 1
解释:
将数组分成2块或者更多块，都无法得到所需的结果。
例如，分成 [5, 4], [3, 2, 1] 的结果是 [4, 5, 1, 2, 3]，这不是有序的数组。

示例 2:

输入: arr = [2,1,3,4,4]
输出: 4
解释:
我们可以把它分成两块，例如 [2, 1], [3, 4, 4]。
然而，分成 [2, 1], [3], [4], [4] 可以得到最多的块数。

注意:

arr 的长度在 [1,2000][1, 2000][1,2000] 之间。

arr[i] 的大小在 [0,108][0, 10^8][0,108] 之间。

贪心 + 构造

一种容易想到的构造方法，是与目标序列（已排升序的数组 clone）做区间比较。

由于题目要求尽可能划分出多的区间，我们可以从前往后处理 arr 和 clone 时统计区间内数的情况，若有 arr[i...j] 和 clone[i...j] 词频完全相同，可知 arr[i...j] 可通过内部排序调整为 clone[i...j]，此时我们将范围 [i...j][i...j][i...j] 划分为一个区间，然后继续往后处理直到整个数组处理完。

Java 代码：

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int[] clone = arr.clone();
        Arrays.sort(clone);
        int n = arr.length, ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0, tot = 0; i < n; i++) {
            int a = arr[i], b = clone[i];
            if (map.getOrDefault(a, 0) == -1) tot--;
            else if (map.getOrDefault(a, 0) == 0) tot++;
            map.put(a, map.getOrDefault(a, 0) + 1);
            if (map.getOrDefault(b, 0) == 1) tot--;
            else if (map.getOrDefault(b, 0) == 0) tot++;
            map.put(b, map.getOrDefault(b, 0) - 1);
            if (tot == 0) ans++;
        }
        return ans;
    }
}

TypeScript 代码：

function maxChunksToSorted(arr: number[]): number {
    let clone = [...arr].sort((a,b)=>a-b)
    let n = arr.length, ans = 0
    const map = new Map<number, number>()
    for (let i = 0, tot = 0; i < n; i++) {
        const a = arr[i], b = clone[i]
        if (!map.has(a)) map.set(a, 0)
        if (map.get(a) == 0) tot++
        else if (map.get(a) == -1) tot--;
        map.set(a, map.get(a) + 1)
        if (!map.has(b)) map.set(b, 0)
        if (map.get(b) == 0) tot++
        else if (map.get(b) == 1) tot--
        map.set(b, map.get(b) - 1)
        if (tot == 0) ans++
    }
    return ans
};