Java?C++題解leetcode769最多能完成排序的塊

更新時間：2022年10月13日 16:39:31 作者：AnjaVon

這篇文章主要為大家介紹了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)

再改進【拜題設限制所賜】

手推一遍上面的執(zhí)行過程發(fā)現(xiàn)最小值沒有什么意義，可以只用最大值衡量，找一個區(qū)間右端點rrr，這個r與arr在[0,r]內(nèi)的最大值相等；

從頭開始統(tǒng)計當前向前區(qū)間內(nèi)的最大值，若該值與遍歷下標相等，則塊滿足題設條件，答案加一；
然后無需進行歸零，因為后續(xù)的所有值一定都大于當前塊的最大值；
重復遍歷與比較。

之所以可以省略最小值的統(tǒng)計，是因為塊的大小由最大值決定，小的值都在前面的塊里被排序，所以一定能在當前塊找到一個與左端點相等的值（最小值）；

此外，當前統(tǒng)計到的最大值既是當前區(qū)間內(nèi)的最大值，也是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
    }
}