Given an array arr [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
[1, 10]
-
arr[i]
[0, 1, ..., arr.length - 1]
這道題給了我們一個長度為n的數組，裡面的數字是[0, n-1]範圍内的所有數字，無序的。現在讓我們分成若幹塊兒，然後給每一小塊兒分别排序，再組合到一起，使原數組變得有序，問我們最多能分多少塊，題目中的兩個例子很好的解釋了題意。我們首先來分析例子1，這是一個倒序的數組，第一個數字是最大的，為4，那麼我們想，這個數字4原本是應該位于數組的最後一個位置，是以中間不可能斷開成新的塊了，要不然數字4就沒法跑到末尾去了。分析到這裡，我們應該隐約有點感覺了，目前數字所在的塊至少要到達坐标為目前數字大小的地方，比如數字4所在的塊至少要包括i=4的那個位置。那麼帶着這個發現，來分析例子2。第一個數字是1，那麼目前數字1所在的塊至少要到 i=1 的位置，然後我們去 i=1 的位置上看，發現是數字0，并沒有超過 i=1 的範圍，那麼前兩個數就可以斷開成一個新的塊兒。再往後看，i=2 的位置是2，可以單獨斷開，後面的3和4也可以分别斷開。是以其實這道題跟Jump Game II那題很像，我們需要維護一個最遠能到達的位置，這裡的每個數字相當于那道題中的跳力，隻有當我們剛好到達最遠點的時候，就可以把之前斷成一個新的塊兒了。
我們周遊原數組，用cur表示能到達的最遠點，然後我們周遊目前位置到cur之間的所有點，周遊的同時如果遇到更大的數字就更新cur，當cur大于等于末尾數字的時候，此時不能再拆分新塊兒了，傳回結果res加1。否則的話說明到達了最遠點，更新第一個for循環的變量i，并且結果res自增1。來看個例子:
[2 0 1 4 3]
當 i=0 時，cur=2，j=1，然後我們發現 j=1 和 j=2 的數字都不會更新cur，且cur也沒有大于等于3，是以此時 j=3 的時候退出了内部的for循環，i指派為2，結果res為1。然後此時 i=3，cur=4，4已經大于末尾的3了，直接傳回res加1，即2，參見代碼如下：
解法一：
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;
}
}; 其實這道題有更霸道的解法，我們仔細觀察一些例子，可以發現斷開為新塊兒的地方都是當之前出現的最大值正好和目前位置坐标相等的地方，比如例子2中，當 i=1 時，之前最大的數字是1，是以可以斷開。而在例子1中，當 i=4 時，才和之前出現過的最大數字4相等，此時斷開也沒啥意義了，因為後面已經沒有數字了，是以還隻是一個塊兒，參見代碼如下：
解法二：
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;
}
}; 讨論：由于本題是其拓展題Max Chunks To Make Sorted II的特殊情況，是以其拓展題的四種解法都可以用在本題，這裡就不一一列舉了，具體的代碼和講解可以參見這個文章Max Chunks To Make Sorted II。
類似題目：
Max Chunks To Make Sorted II
Jump Game II
參考資料：
https://leetcode.com/problems/max-chunks-to-make-sorted/solution/
LeetCode All in One 題目講解彙總(持續更新中...)
喜歡請點贊，疼愛請打賞❤️~.~ 微信打賞  | Venmo 打賞  |