[LeetCode] 769.Max Chunks To Make Sorted 可排序的最大塊數(shù)

Given an array arr that is a permutation of [0, 1, ..., arr.length - 1], we split the array into some number of "chunks" (partitions), and individually sort each chunk.  After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

Example 1:

Input: arr = [4,3,2,1,0]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn't sorted.

Example 2:

Input: arr = [1,0,2,3,4]
Output: 4
Explanation:
We can split into two chunks, such as [1, 0], [2, 3, 4].
However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.

Note:

• arr will have length in range [1, 10].
• arr[i] will be a permutation of [0, 1, ..., arr.length - 1].

這道題給了我們一個(gè)長(zhǎng)度為n的數(shù)組，里面的數(shù)字是[0, n-1]范圍內(nèi)的所有數(shù)字，無(wú)序的?，F(xiàn)在讓我們分成若干塊兒，然后給每一小塊兒分別排序，再組合到一起，使原數(shù)組變得有序，問(wèn)我們最多能分多少塊，題目中的兩個(gè)例子很好的解釋了題意。我們首先來(lái)分析例子1，這是一個(gè)倒序的數(shù)組，第一個(gè)數(shù)字是最大的，為4，那么我們想，這個(gè)數(shù)字4原本是應(yīng)該位于數(shù)組的最后一個(gè)位置，所以中間不可能斷開(kāi)成新的塊了，要不然數(shù)字4就沒(méi)法跑到末尾去了。分析到這里，我們應(yīng)該隱約有點(diǎn)感覺(jué)了，當(dāng)前數(shù)字所在的塊至少要到達(dá)坐標(biāo)為當(dāng)前數(shù)字大小的地方，比如數(shù)字4所在的塊至少要包括i=4的那個(gè)位置。那么帶著這個(gè)發(fā)現(xiàn)，來(lái)分析例子2。第一個(gè)數(shù)字是1，那么當(dāng)前數(shù)字1所在的塊至少要到 i=1 的位置，然后我們?nèi)?i=1 的位置上看，發(fā)現(xiàn)是數(shù)字0，并沒(méi)有超過(guò) i=1 的范圍，那么前兩個(gè)數(shù)就可以斷開(kāi)成一個(gè)新的塊兒。再往后看，i=2 的位置是2，可以單獨(dú)斷開(kāi)，后面的3和4也可以分別斷開(kāi)。所以其實(shí)這道題跟Jump Game II那題很像，我們需要維護(hù)一個(gè)最遠(yuǎn)能到達(dá)的位置，這里的每個(gè)數(shù)字相當(dāng)于那道題中的跳力，只有當(dāng)我們剛好到達(dá)最遠(yuǎn)點(diǎn)的時(shí)候，就可以把之前斷成一個(gè)新的塊兒了。

我們遍歷原數(shù)組，用cur表示能到達(dá)的最遠(yuǎn)點(diǎn)，然后我們遍歷當(dāng)前位置到cur之間的所有點(diǎn)，遍歷的同時(shí)如果遇到更大的數(shù)字就更新cur，當(dāng)cur大于等于末尾數(shù)字的時(shí)候，此時(shí)不能再拆分新塊兒了，返回結(jié)果res加1。否則的話說(shuō)明到達(dá)了最遠(yuǎn)點(diǎn)，更新第一個(gè)for循環(huán)的變量i，并且結(jié)果res自增1。來(lái)看個(gè)例子:

[2 0 1 4 3]

當(dāng) i=0 時(shí)，cur=2，j=1，然后我們發(fā)現(xiàn) j=1 和 j=2 的數(shù)字都不會(huì)更新cur，且cur也沒(méi)有大于等于3，所以此時(shí) j=3 的時(shí)候退出了內(nèi)部的for循環(huán)，i賦值為2，結(jié)果res為1。然后此時(shí) i=3，cur=4，4已經(jīng)大于末尾的3了，直接返回res加1，即2，參見(jiàn)代碼如下：

解法一：

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int res = 0, n = arr.size();
        for (int i = 0; i < n; ++i) {
            int cur = arr[i], j = i + 1;
            for (; j <= cur; ++j) {
                cur = max(cur, arr[j]);
                if (cur >= arr.back()) return res + 1;
            }
            i = j - 1;
            ++res;
        }
        return res;
    }
};

其實(shí)這道題有更霸道的解法，我們仔細(xì)觀察一些例子，可以發(fā)現(xiàn)斷開(kāi)為新塊兒的地方都是當(dāng)之前出現(xiàn)的最大值正好和當(dāng)前位置坐標(biāo)相等的地方，比如例子2中，當(dāng) i=1 時(shí)，之前最大的數(shù)字是1，所以可以斷開(kāi)。而在例子1中，當(dāng) i=4 時(shí)，才和之前出現(xiàn)過(guò)的最大數(shù)字4相等，此時(shí)斷開(kāi)也沒(méi)啥意義了，因?yàn)楹竺嬉呀?jīng)沒(méi)有數(shù)字了，所以還只是一個(gè)塊兒，參見(jiàn)代碼如下： 

解法二：

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int res = 0, n = arr.size(), mx = 0;
        for (int i = 0; i < n; ++i) {
            mx = max(mx, arr[i]);
            if (mx == i) ++res;
        }
        return res;
    }
};

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(769.可排序的最大塊數(shù))的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)可排序的最大塊數(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論