C++可排序的最大塊數(shù)問題怎么解決

這篇文章主要講解了“C++可排序的最大塊數(shù)問題怎么解決”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“C++可排序的最大塊數(shù)問題怎么解決”吧！

可排序的最大塊數(shù)

This question is the same as "Max Chunks to Make Sorted" except the integers of the given array are not necessarily distinct, the input array could be up to length 2000, and the elements could be up to 10**8.

Given an array arr of integers (not necessarily distinct), 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 = [5,4,3,2,1]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn"t sorted.

Example 2:

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

Note:

• arr will have length in range [1, 2000].

• arr[i] will be an integer in range [0, 10**8].

這道題是之前那道 Max Chunks To Make Sorted 的拓展，那道題說了數(shù)組是[0, n-1]中所有數(shù)字的一種全排列，n為數(shù)組的長度。而這道題的數(shù)字就沒有這種限制，可以是大于n的數(shù)字，也可以有重復(fù)的數(shù)字。由于數(shù)字和坐標(biāo)不再有太多的關(guān)聯(lián)，所以之前那題中比較數(shù)字和坐標(biāo)的大小的解法肯定行不通了。我們來看一種十分巧妙的解法，首先我們需要明確的一點(diǎn)是，拆分后的塊兒排序后拼在一起會跟原數(shù)組相同，我們用一個例子來說明：

2  1  4  3  4

1  2  3  4  4

1  2  3  4  4

我們看到第一行是原數(shù)組，第二行是排序后并拼接在了一起的塊兒，不同的顏色代表不同的塊兒，而第三行是直接對原數(shù)組排序后的結(jié)果。仔細(xì)觀察可以發(fā)現(xiàn)，能形成塊兒的數(shù)字之和跟排序后的數(shù)組的相同長度的子數(shù)組的數(shù)字之和是相同的。比如第一個塊兒是數(shù)字2和1，和為3，而排序后的前兩個數(shù)字為1和2，和也是3，那么我們就知道原數(shù)組的前兩個數(shù)字可以拆成一個塊兒。同理，原數(shù)組中的第三個和第四個數(shù)字分別為4和3，和為7，而排序后的數(shù)組對應(yīng)位置的數(shù)字之和也是7，說明可以拆分出塊兒。需要注意的是，在累加數(shù)組和的時(shí)候有可能會超過整型最大值，所以我們用長整型來保存就可以了。就是這么簡單而暴力的思路，時(shí)間復(fù)雜度為O(nlgn)，主要花在給數(shù)組排序上了。由于本題是 Max Chunks To Make Sorted 的generalized的情況，所以這種解法自然也可以解決之前那道題了，不過就是時(shí)間復(fù)雜度稍高了一些，參見代碼如下：

解法一：

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        long res = 0, sum1 = 0, sum2 = 0;
        vector<int> expect = arr;
        sort(expect.begin(), expect.end());
        for (int i = 0; i < arr.size(); ++i) {
            sum1 += arr[i];
            sum2 += expect[i];
            if (sum1 == sum2) ++res;
        }
        return res;
    }
};

這道題的時(shí)間復(fù)雜度可以優(yōu)化到線性，不過就是需要花點(diǎn)空間。下面這種解法也相當(dāng)?shù)那擅?，我們需要兩個數(shù)組forward和backward，其中 foward[i] 表示 [0, i] 范圍內(nèi)最大的數(shù)字，而 backward[i] 表示 [i, n-1] 范圍內(nèi)最小的數(shù)字，實(shí)際上就是要知道已經(jīng)遍歷過的最大值，和還未遍歷的到的最小值。為啥我們對這兩個值感興趣呢？這是本解法的精髓所在，我們知道可以拆分為塊兒的前提是之后的數(shù)字不能比當(dāng)前塊兒中的任何數(shù)字小，不然那個較小的數(shù)字就無法排到前面。就像例子1，為啥不能拆出新塊兒，就因?yàn)樽钚〉臄?shù)字在末尾。那么這里我們能拆出新塊兒的條件就是，當(dāng)前位置出現(xiàn)過的最大值小于等于之后還未遍歷到的最小值時(shí)，就能拆出新塊兒。比如例子2中，當(dāng) i=1 時(shí)，此時(shí)出現(xiàn)過的最大數(shù)字為2，未遍歷到的數(shù)字中最小值為3，所以可以拆出新塊兒，參見代碼如下：

解法二：

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

我們可以優(yōu)化一下空間復(fù)雜度，因?yàn)槲覀兛梢栽诒闅v的過程中維護(hù)一個當(dāng)前最大值curMax，所以就不用一個專門的forward數(shù)組了，但是backward數(shù)組還是要的，參見代碼如下： 

解法三：

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

下面這種使用單調(diào)棧Monotonous Stack的解法的題也十分的巧妙，我們維護(hù)一個單調(diào)遞增的棧，遇到大于等于棧頂元素的數(shù)字就壓入棧，當(dāng)遇到小于棧頂元素的數(shù)字后，處理的方法很是巧妙?。菏紫热〕鰲ｍ斣?，這個是當(dāng)前最大值，因?yàn)槲覀兙S護(hù)的就是單調(diào)遞增棧啊，然后我們再進(jìn)行循環(huán)，如果棧不為空，且新的棧頂元素大于當(dāng)前數(shù)字，則移除棧頂元素。這步簡直絕了，這里我們單調(diào)棧的元素個數(shù)實(shí)際上是遍歷到當(dāng)前數(shù)字之前可以拆分成的塊兒的個數(shù)，我們遇到一個大于棧頂?shù)脑兀蛯⑵鋲喝霔?，suppose其是一個新塊兒的開頭，但是一旦后面遇到小的數(shù)字了，我們就要反過來檢查前面的數(shù)字，有可能我們之前認(rèn)為的可以拆分成塊兒的地方，現(xiàn)在就不能拆了，舉個栗子來說吧：

比如數(shù)組為 [1 0 3 3 2]，我們先把第一個數(shù)字1壓入棧，此時(shí)棧為：

stack：1

然后遍歷到第二個數(shù)字0，發(fā)現(xiàn)小于棧頂元素，將棧頂元素1取出存入curMax，此時(shí)棧為空了，不做任何操作，將curMax壓回棧，此時(shí)棧為：

stack：1

然后遍歷到第三個數(shù)字3，大于棧頂元素，壓入棧，此時(shí)棧為：

stack：1，3

然后遍歷到第四個數(shù)字3，等于棧頂元素，壓入棧，此時(shí)棧為：

stack：1，3，3

然后遍歷到第五個數(shù)字2，小于棧頂元素，將棧頂元素3取出存入curMax，此時(shí)新的棧頂元素3，大于當(dāng)前數(shù)字2，移除此棧頂元素3，然后新的棧頂元素1，小于當(dāng)前數(shù)字2，循環(huán)結(jié)束，將curMax壓回棧，此時(shí)棧為：

stack：1，3

所以最終能拆為兩個塊兒，即stack中數(shù)字的個數(shù)，參見代碼如下：

解法四：

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        stack<int> st;
        for (int i = 0; i < arr.size(); ++i) {
            if (st.empty() || st.top() <= arr[i]) {
                st.push(arr[i]);
            } else {
                int curMax = st.top(); st.pop();
                while (!st.empty() && st.top() > arr[i]) st.pop();
                st.push(curMax);
            }
        }
        return st.size();
    }
};

感謝各位的閱讀，以上就是“C++可排序的最大塊數(shù)問題怎么解決”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對C++可排序的最大塊數(shù)問題怎么解決這一問題有了更深刻的體會，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識點(diǎn)的文章，歡迎關(guān)注！