湖北省网站建设_网站建设公司_原型设计_seo优化

Problem: 769. Max Chunks To Make Sorted 最多能完成排序的块

解题过程

耗时100%，最多的块只需要满足一段区间内的数字排序以后可以不用移动即可，双指针，l 最小值，r 最大值，start 这个区间的起始数字，从左向右的，若满足 i == 最大值 r，且i-start == r - l，那么就满足这段区间的这些数字刚好是排序以后的数字集合，可以做一个块，若i+1还在索引内，就让start = l = ++r，计数num++

Code

class Solution { public: int maxChunksToSorted(vector<int>& arr) { int l = 10, r = -1, start = 0, num = 1; for(int i = 0; i < arr.size(); i++) { if(r < arr[i]) { r = arr[i]; } if(l > arr[i]) { l = arr[i]; } if(i==r && i - start == r - l) { if(i + 1 < arr.size()) { start = l = ++r; num++; continue; } } } return num; } };