java?LeetCode刷題稍有難度的貪心構(gòu)造算法

更新時間：2023年02月03日 10:23:13 作者：宮水三葉的刷題日記

這篇文章主要為大家介紹了java?LeetCode刷題稍有難度的貪心構(gòu)造題解示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目描述

這是 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)計(jì)區(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
};