Q1. 是否能用貪心算法？為什么？

? ? ? ?先預(yù)設(shè)一個(gè)策略，每當(dāng)當(dāng)前的nums[i]滿足可以? "成塊"，就直接讓這個(gè)數(shù)成塊，也就是說之后的遍歷過程中不會(huì)將這個(gè)數(shù)在考慮到自己的塊內(nèi)，

????????"成塊" 是指只要只需要將nums[i]放到前面的某個(gè)子數(shù)組的尾部，然后將這個(gè)子數(shù)組進(jìn)行排序，就能得到一個(gè)擁有連續(xù)自然數(shù)的子數(shù)組，就稱為成塊

? ? ? ?能夠使用談心算法是因?yàn)橛腥缦乱?guī)律

? ? ? ?規(guī)律1. 以nums[i]為結(jié)尾的成塊的子數(shù)組，其中的最大值不能小于 i

? ? ? ? ? ? ? ? ?反證法：假設(shè)nums[i]為結(jié)尾的成塊的子數(shù)組，其中最大值小于?i

? ? ? ? ? ? ? ? 那么對(duì)這個(gè)子數(shù)組進(jìn)行排序后，最后一個(gè)值即為maxval，且其下標(biāo)標(biāo)定位i

? ? ? ? ? ? ? ? 子數(shù)組最開始的那個(gè)下標(biāo)設(shè)為j, 那么子數(shù)組中應(yīng)該有 i - j + 1個(gè)元素

? ? ? ? ? ? ? ? 又根據(jù)成塊的定義，這里將會(huì)缺少自然數(shù)填滿i - j + 1個(gè)位置矛盾

? ? ? ? ? ? ? ? 故，想要成塊，子數(shù)組的最大值不能小于 i?

下面以圖示的方法進(jìn)一步說明，假設(shè)紅線前的0 1 2已經(jīng)成塊了

如果 nums[7] < 7 那么一定不能成塊，因?yàn)榇藭r(shí)只能有 6 5 4 3 2 1 0 能放入這8個(gè)黑框中，

????????規(guī)律2. 以nums[i]為結(jié)尾的成塊的子數(shù)組，其中的最大值不能大于 i

? ? ? ? ? ? ? ? 證明與上面類似，矛盾之處在于如果最大值大于 i ，則將會(huì)多出來一個(gè)元素

所以要想成塊只能是maxval == i

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