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

题目要求

思路：模拟

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

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

总结

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

以上就是Java C++题解leetcode769最多能完成排序的块的详细内容，更多关于Java C++最多能完成排序的块的资料请关注猪先飞其它相关文章！