每日一题做题记录，参考官方和三叶的题解

题目要求

思路：模拟

• 由题意可知，分块内的值区间应当满足与其所在下标区间一致，也就是说valuemax=indexmax,valuemin=indexminvalue_{max}=index_{max},value_{min}=index_{min}valuemax​=indexmax​,valuemin​=indexmin​；
• 那么用两个指针分别指向当前块的左右下标，并记录区间内最值，若左指针下标和右指针下标恰与区间最值分别相等，即l=min,r=maxl=min,r=maxl=min,r=max，那么该块满足题设要求，答案加一。

Java

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int n = arr.length, res = 0;
        int min = n, max = -1;
        for (int r = 0, l = 0; r < n; r++) {
            min = Math.min(min, arr[r]);
            max = Math.max(max, arr[r]);
            if (l == min && r == max) {
                res++;
                l = r + 1;
                min = n;
            }
        }
        return res;
    }
}

• 时间复杂度：O(n)O(n)O(n)
• 空间复杂度：O(1)O(1)O(1)

再改进【拜题设限制所赐】

• 手推一遍上面的执行过程发现最小值没有什么意义，可以只用最大值衡量，找一个区间右端点rrr，这个rrr与arrarrarr在[0,r][0,r][0,r]内的最大值相等；
  • 从头开始统计当前向前区间内的最大值，若该值与遍历下标相等，则块满足题设条件，答案加一；
  • 然后无需进行归零，因为后续的所有值一定都大于当前块的最大值；
  • 重复遍历与比较。
• 之所以可以省略最小值的统计，是因为块的大小由最大值决定，小的值都在前面的块里被排序，所以一定能在当前块找到一个与左端点相等的值（最小值）；
  • 此外，当前统计到的最大值既是当前区间内的最大值，也是arrarrarr从头至此的最大值。

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int res = 0, max = -1;
        for (int r = 0; r < arr.length; r++) {
            max = Math.max(max, arr[r]);
            if (r == max)
                res++;
        }
        return res;
    }
}

• 时间复杂度：O(n)O(n)O(n)
• 空间复杂度：O(1)O(1)O(1)

C++

• 第一万次注意maxmaxmax变量和maxmaxmax方法的命名冲突……

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int res = 0, maxx = -1;
        for (int r = 0; r < arr.size(); r++) {
            maxx = max(maxx, arr[r]);
            if (r == maxx)
                res++;
        }
        return res;
    }
};

• 时间复杂度：O(n)O(n)O(n)
• 空间复杂度：O(1)O(1)O(1)

Rust

impl Solution {
    pub fn max_chunks_to_sorted(arr: Vec<i32>) -> i32 {
        let (mut res, mut maxx) = (0, -1);
        for r in 0..arr.len() {
            maxx = maxx.max(arr[r]);
            if r as i32 == maxx {
                res += 1;
            }
        }
        res
    }
}

• 时间复杂度：O(n)O(n)O(n)
• 空间复杂度：O(1)O(1)O(1)

总结

• 简单到没什么好总结的……题设的限制极大地降低了题目难度，本来看题还没有意识到，看到示例就意识到了今天可以拥有简单题的快乐~
• 看官方的题解管这个再改进方法叫贪心，分析了好长好长……看着就头疼
• 还有其他解法用栈的，本质上思路一样，是理解比较浅但实现稍复杂的方法。

欢迎指正与讨论！