Java C++题解leetcode915分割数组示例-C/C++开发

这篇文章主要为大家介绍了JavaC++题解leetcode915分割数组示例详解，有需要的朋友可以借鉴参考下，希望能够有所帮助，祝大家多多进步，早日升职加薪

题目要求

题目链接

思路一：两次遍历

题目的意思也就是左半边数组的最大值小于等于右半边数组的最小值，那么就找这个分界点就好；

首先从后向前遍历，找[i,n−1]里最小的值；
然后从前向后遍历，找[0,i]里最大的值；
然后找满足max[i]<=min[i+1]的分割点i；
可以将2、3两步结合为一步完成，由于iii从前向后不断增大，所以用后面（较大）的值覆盖更新之前的值。

找到分界点的索引后，只需+1即可得到长度。

Java

class Solution {
    public int partitionDisjoint(int[] nums) {
        int n = nums.length;
        int[] minn = new int[n + 10];
        minn[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--)
            minn[i] = Math.min(minn[i + 1], nums[i]);
        for (int i = 0, maxx = 0; i < n - 1; i++) {
            maxx = Math.max(maxx, nums[i]);
            if (maxx <= minn[i + 1])
                return i + 1;
        }
        return 1; // 用例保证不出现
    }
}

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

C++

class Solution {
public:
    int partitionDisjoint(vector<int>& nums) {
        int n = nums.size();
        int minn[n + 10];
        minn[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--)
            minn[i] = min(minn[i + 1], nums[i]);
        for (int i = 0, maxx = 0; i < n - 1; i++) {
            maxx = max(maxx, nums[i]);
            if (maxx <= minn[i + 1])
                return i + 1;
        }
        return 1; // 用例保证不出现
    }
};

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

Rust

impl Solution {
    pub fn partition_disjoint(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut minn = vec![nums[n - 1]; n + 10];
        for i in (0..(n - 1)).rev() {
            minn[i] = minn[i + 1].min(nums[i]);
        }
        let mut maxx = 0;
        for i in 0..(n - 1) {
            maxx = maxx.max(nums[i]);
            if (maxx <= minn[i + 1]) {
                return (i + 1) as i32;
            }
        }
        return 1; // 用例保证不出现
    }
}

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

思路二：一次遍历

从前向后遍历每个节点，依次假设每个节点为最终分界点；

维护当前遍历节点的最大值maxx，即[0,i]内；
记录假设分界点i及其对应左半边数组最大值leftMax；

若当前值nums[i]<leftMax则重新划定分界，将当前节点纳入左区间；

找到最终结果节点索引值，将其+1即得答案。

Java

class Solution {
    public int partitionDisjoint(int[] nums) {
        int leftMax = nums[0], res = 0, maxx = nums[0];
        for (int i = 1; i < nums.length - 1; i++) {
            maxx = Math.max(maxx, nums[i]);
            if (nums[i] < leftMax) {
                leftMax = maxx;
                res = i;
            }
        }
        return res + 1;
    }
}

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

C++

class Solution {
public:
    int partitionDisjoint(vector<int>& nums) {
        int leftMax = nums[0], res = 0, maxx = nums[0];
        for (int i = 1; i < nums.size() - 1; i++) {
            maxx = max(maxx, nums[i]);
            if (nums[i] < leftMax) {
                leftMax = maxx;
                res = i;
            }
        }
        return res + 1;
    }
};

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

Rust

impl Solution {
    pub fn partition_disjoint(nums: Vec<i32>) -> i32 {
        let (mut leftMax, mut res, mut maxx) = (nums[0], 0, nums[0]);
        for i in 1..(nums.len()-1) {
            maxx = maxx.max(nums[i]);
            if nums[i] < leftMax {
                leftMax = maxx;
                res = i as i32;
            }
        }
        res + 1
    }
}