当前位置 : 主页 > 编程语言 > java >

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

来源:互联网 收集:自由互联 发布时间:2023-01-30
目录 题目要求 思路:模拟 Java C++ Rust 总结 题目要求 思路:模拟 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
目录
  • 题目要求
  • 思路:模拟
  • Java
    • C++
    • Rust
  • 总结

    题目要求

    思路:模拟

    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++最多能完成排序的块的资料请关注自由互联其它相关文章!

    网友评论