宫水三叶的刷题日记

V1

2022/08/13阅读:22主题:前端之巅同款

768. 最多能完成排序的块 II : 常规贪心构造题

题目描述

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

Tag : 「贪心」

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

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 的长度在 之间。
  • arr[i] 的大小在 之间。

贪心 + 构造

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

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

容易证明该做法的正确性:可从边界开始进行归纳分析,起始两者均从下标为 的位置进行扫描。假设最优解和贪心解的第一个区间的结束位置相同,问题就会归结到子问题上(即双方均从相同的子数组起始位置开始构造),因此无须额外证明;而当起始位置相同,结束位置不同时,假设分别为 ,则必然有 (因为如果有 ,那么在 扫描到 位置时已经满足划分区间的条件,已经会停下来,即与贪心决策逻辑冲突),而当 时,我们可以将最优解中的区间 进一步划分为 两段,同时不影响后续的构造过程,使得最终划分的区间数增大,即与最优解本身无法划分冲突。

根据数值之间满足严格全序,可知当 均不满足时,必然有 为真。

综上,我们证明了对于相同起点,贪心解与最优解结束位置必然相同,从而证明贪心解区间数与最优解相等。

于是原问题转换为如何快速对两数组(原数组 arr 和目标数组 clone)进行词频比较,由于数值的范围为 ,如果使用最裸的词频对比方案的话,需要先进行离散化,最终算法的复杂度为 。而更好的解决方案是使用哈希表进行计数,同时维护当前计数不为 的数值数量 tot,具体的,当我们处理 时,我们在哈希表中对 进行计数加一,而在处理 时,对 进行计数减一。从而将词频比较的复杂度从 下降到

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<numbernumber>()
    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
};
  • 时间复杂度:
  • 空间复杂度:

最后

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

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

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

分类:

后端

标签:

后端

作者介绍

宫水三叶的刷题日记
V1