快捷導(dǎo)航

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

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

這篇文章主要為大家介紹了Java?C++題解leetcode769最多能完成排序的塊示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目要求

思路：模擬

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

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)

再改進(jìn)【拜題設(shè)限制所賜】

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

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

之所以可以省略最小值的統(tǒng)計(jì)，是因?yàn)閴K的大小由最大值決定，小的值都在前面的塊里被排序，所以一定能在當(dāng)前塊找到一個(gè)與左端點(diǎn)相等的值（最小值）；

此外，當(dāng)前統(tǒng)計(jì)到的最大值既是當(dā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;
    }
}

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：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;
    }
};

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：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
    }
}

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)

總結(jié)

簡(jiǎn)單到?jīng)]什么好總結(jié)的……題設(shè)的限制極大地降低了題目難度，本來看題還沒有意識(shí)到，看到示例就意識(shí)到了今天可以擁有簡(jiǎn)單題的快樂~
看官方的題解管這個(gè)再改進(jìn)方法叫貪心，分析了好長(zhǎng)好長(zhǎng)……看著就頭疼
還有其他解法用棧的，本質(zhì)上思路一樣，是理解比較淺但實(shí)現(xiàn)稍復(fù)雜的方法。

以上就是Java C++題解leetcode769最多能完成排序的塊的詳細(xì)內(nèi)容，更多關(guān)于Java C++最多能完成排序的塊的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: