关于后端:768-最多能完成排序的块-II-常规贪心构造题

这是 LeetCode 上的 768. 最多能实现排序的块 II，难度为艰难。

Tag :「贪婪」

这个问题和“最多能实现排序的块”类似，但给定数组中的元素能够反复，输出数组最大长度为 $2000$，其中的元素最大为 $10^8$。

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]$ 之间。
arr[i] 的大小在 $[0, 10^8]$ 之间。

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

因为题目要求尽可能划分出多的区间，咱们能够从前往后解决 arr 和 clone 时统计区间内数的状况，若有 arr[i...j] 和 clone[i...j] 词频完全相同，可知 arr[i...j] 可通过外部排序调整为 clone[i...j]，此时咱们将范畴 $[i…j]$ 划分为一个区间，而后持续往后解决直到整个数组解决完。

容易证实该做法的正确性：可从边界开始进行演绎剖析，起始两者均从下标为 $0$ 的地位进行扫描。假如最优解和贪婪解的第一个区间的完结地位雷同，问题就会归结到子问题上（即单方均从雷同的子数组起始地位开始结构），因而毋庸额定证实；而当起始地位雷同，完结地位不同时，假如别离为 $clone[i…j_1]$ 和 $arr[i…j_2]$，则必然有 $j_1 > j_2$（因为如果有 $j_1 < j_2$，那么在 $arr$ 扫描到 $j_1$ 地位时曾经满足划分区间的条件，曾经会停下来，即与贪婪决策逻辑抵触），而当 $j_1 > j_2$ 时，咱们能够将最优解中的区间 $clone[i…j_1]$ 进一步划分为 $clone[i…j_2]$ 和 $clone[j_2+1 … j_1]$ 两段，同时不影响后续的结构过程，使得最终划分的区间数增大，即与最优解自身无奈划分抵触。

依据数值之间满足严格全序，可知当 $j_1 > j_2$ 和 $j_1 < j_2$ 均不满足时，必然有 $j_1 = j_2$ 为真。

综上，咱们证实了对于雷同终点，贪婪解与最优解完结地位必然雷同，从而证实贪婪解区间数与最优解相等。

于是原问题转换为如何疾速对两数组（原数组 arr 和指标数组 clone）进行词频比拟，因为数值的范畴为 $10^8$，如果应用最裸的词频比照计划的话，须要先进行离散化，最终算法的复杂度为 $O(n\log{n} + n^2)$。而更好的解决方案是应用哈希表进行计数，同时保护以后计数不为 $0$ 的数值数量 tot，具体的，当咱们解决 $arr[i]$ 时，咱们在哈希表中对 $arr[i]$ 进行计数加一，而在解决 $clone[i]$ 时，对 $clone[i]$ 进行计数减一。从而将词频比拟的复杂度从 $O(n^2)$ 降落到 $O(n)$。

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
};

工夫复杂度：$O(n\log{n})$
空间复杂度：$O(n)$

这是咱们「刷穿 LeetCode」系列文章的第 No.768 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的合集新基地 🎉🎉

本文由 mdnice 多平台公布

关于后端:768-最多能完成排序的块-II-常规贪心构造题

题目形容

贪婪 + 结构

最初