Leetcode 769. Max Chunks To Make Sorted (python+cpp)

题目

解析

这道题的关键在于找到当前位置以前的最大值和现在所处位置的关系。要排序后连接顺序一样的同意表达为，分出来的区间需满足：前一个区间最大值不得大于后一个区间最小值。再进一步推理就是，当前区间的最大值一定不能比当前位置要大。不然的话，由于是n个不重复的数字，当前的最大值一定会比后一个区间某个值大，就不符合提议了。所以求解过程如下：

• 记录当前最大值，跟当前位置比较，如果当前位置等于当前位置最大值的时候，就可以进行一次分割
  python版本如下：

class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        curr_max = 0
        count = 0
        for i in range(len(arr)):
            curr_max = max(curr_max,arr[i])
            if curr_max == i:
                count+=1
        return count

C++版本如下：

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