Java C++题解leetcode769最多能完成排序的块

Java C++最多能完成排序的块 LeetCode最多能完成排序的块 2022-11-13 18:11:08 211人浏览薄情痞子

摘要

目录题目要求思路：模拟Javac++Rust总结题目要求思路：模拟 Java class Solution { public int maxChunksToSorted

题目要求

思路：模拟

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(1)

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

手推一遍上面的执行过程发现最小值没有什么意义，可以只用最大值衡量，找一个区间右端点rrr，这个r与arr在[0,r]内的最大值相等；

从头开始统计当前向前区间内的最大值，若该值与遍历下标相等，则块满足题设条件，答案加一；
然后无需进行归零，因为后续的所有值一定都大于当前块的最大值；
重复遍历与比较。

之所以可以省略最小值的统计，是因为块的大小由最大值决定，小的值都在前面的块里被排序，所以一定能在当前块找到一个与左端点相等的值（最小值）；

此外，当前统计到的最大值既是当前区间内的最大值，也是arr从头至此的最大值。

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(1)

C++

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

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(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
    }
}