C++實現LeetCode(768.可排序的最大塊數之二)

Posted on by

[LeetCode] 768.Max Chunks To Make Sorted II 可排序的最大塊數之二

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 的拓展，那道題說瞭數組是[0, n-1]中所有數字的一種全排列，n為數組的長度。而這道題的數字就沒有這種限制，可以是大於n的數字，也可以有重復的數字。由於數字和坐標不再有太多的關聯，所以之前那題中比較數字和坐標的大小的解法肯定行不通瞭。我們來看一種十分巧妙的解法，首先我們需要明確的一點是，拆分後的塊兒排序後拼在一起會跟原數組相同，我們用一個例子來說明：

2  1  4  3  4

1  2  3  4  4

1  2  3  4  4

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

解法一：

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

這道題的時間復雜度可以優化到線性，不過就是需要花點空間。下面這種解法也相當的巧妙，我們需要兩個數組forward和backward，其中 foward[i] 表示 [0, i] 范圍內最大的數字，而 backward[i] 表示 [i, n-1] 范圍內最小的數字，實際上就是要知道已經遍歷過的最大值，和還未遍歷的到的最小值。為啥我們對這兩個值感興趣呢？這是本解法的精髓所在，我們知道可以拆分為塊兒的前提是之後的數字不能比當前塊兒中的任何數字小，不然那個較小的數字就無法排到前面。就像例子1，為啥不能拆出新塊兒，就因為最小的數字在末尾。那麼這裡我們能拆出新塊兒的條件就是，當前位置出現過的最大值小於等於之後還未遍歷到的最小值時，就能拆出新塊兒。比如例子2中，當 i=1 時，此時出現過的最大數字為2，未遍歷到的數字中最小值為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;
    }
};

我們可以優化一下空間復雜度，因為我們可以在遍歷的過程中維護一個當前最大值curMax，所以就不用一個專門的forward數組瞭，但是backward數組還是要的，參見代碼如下： 

解法三：

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

下面這種使用單調棧Monotonous Stack的解法的題也十分的巧妙，我們維護一個單調遞增的棧，遇到大於等於棧頂元素的數字就壓入棧，當遇到小於棧頂元素的數字後，處理的方法很是巧妙啊：首先取出棧頂元素，這個是當前最大值，因為我們維護的就是單調遞增棧啊，然後我們再進行循環，如果棧不為空，且新的棧頂元素大於當前數字，則移除棧頂元素。這步簡直絕瞭，這裡我們單調棧的元素個數實際上是遍歷到當前數字之前可以拆分成的塊兒的個數，我們遇到一個大於棧頂的元素，就將其壓入棧，suppose其是一個新塊兒的開頭，但是一旦後面遇到小的數字瞭，我們就要反過來檢查前面的數字，有可能我們之前認為的可以拆分成塊兒的地方，現在就不能拆瞭，舉個栗子來說吧：

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

stack：1

然後遍歷到第二個數字0，發現小於棧頂元素，將棧頂元素1取出存入curMax，此時棧為空瞭，不做任何操作，將curMax壓回棧，此時棧為：

stack：1

然後遍歷到第三個數字3，大於棧頂元素，壓入棧，此時棧為：

stack：1，3

然後遍歷到第四個數字3，等於棧頂元素，壓入棧，此時棧為：

stack：1，3，3

然後遍歷到第五個數字2，小於棧頂元素，將棧頂元素3取出存入curMax，此時新的棧頂元素3，大於當前數字2，移除此棧頂元素3，然後新的棧頂元素1，小於當前數字2，循環結束，將curMax壓回棧，此時棧為：

stack：1，3

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

解法四：

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++實現LeetCode(768.可排序的最大塊數之二)的文章就介紹到這瞭,更多相關C++實現可排序的最大塊數之二內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：