題目描述

這是 LeetCode 上的 768. 最多能完成排序的塊 II ，難度為 困難。

Tag : 「貪心」

這個問題和“最多能完成排序的塊”相似，但給定數(shù)組中的元素可以重復(fù)，輸入數(shù)組最大長度為 200020002000，其中的元素最大為 10810^8108。

arr 是一個可能包含重復(fù)元素的整數(shù)數(shù)組，我們將這個數(shù)組分割成幾個“塊”，并將這些塊分別進(jìn)行排序。之后再連接起來，使得連接的結(jié)果和按升序排序后的原數(shù)組相同。

我們最多能將數(shù)組分成多少塊？

示例 1:

輸入: arr = [5,4,3,2,1]
輸出: 1
解釋:
將數(shù)組分成2塊或者更多塊，都無法得到所需的結(jié)果。
例如，分成 [5, 4], [3, 2, 1] 的結(jié)果是 [4, 5, 1, 2, 3]，這不是有序的數(shù)組。 

示例 2:

輸入: arr = [2,1,3,4,4]
輸出: 4
解釋:
我們可以把它分成兩塊，例如 [2, 1], [3, 4, 4]。
然而，分成 [2, 1], [3], [4], [4] 可以得到最多的塊數(shù)。 

注意:

arr 的長度在 [1,2000][1, 2000][1,2000] 之間。

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

貪心 + 構(gòu)造

一種容易想到的構(gòu)造方法，是與目標(biāo)序列（已排升序的數(shù)組 clone）做區(qū)間比較。

由于題目要求盡可能劃分出多的區(qū)間，我們可以從前往后處理 arr 和 clone 時統(tǒng)計區(qū)間內(nèi)數(shù)的情況，若有 arr[i...j] 和 clone[i...j] 詞頻完全相同，可知 arr[i...j] 可通過內(nèi)部排序調(diào)整為 clone[i...j]，此時我們將范圍 [i...j][i...j][i...j] 劃分為一個區(qū)間，然后繼續(xù)往后處理直到整個數(shù)組處理完。

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

• 時間復(fù)雜度：O(nlog?n)
• 空間復(fù)雜度：O(n)

最后

這是我們「刷穿 LeetCode」系列文章的第 No.768 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們將先把所有不帶鎖的題目刷完。

在這個系列文章里面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應(yīng)的代碼模板。

為了方便各位同學(xué)能夠電腦上進(jìn)行調(diào)試和提交代碼，我建立了相關(guān)的倉庫：github.com/SharingSour… 。

在倉庫地址里，你可以看到系列文章的題解鏈接、系列文章的相應(yīng)代碼、LeetCode 原題鏈接和其他優(yōu)選題解。

以上就是java LeetCode刷題稍有難度的貪心構(gòu)造的詳細(xì)內(nèi)容，更多關(guān)于java LeetCode貪心構(gòu)造的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論