给网友们整理相关的编程文章，网友步锐泽根据主题投稿了本篇教程内容，涉及到Java、C++题解分割数组、Java、C++、LeetCode、分割数组、Java C++题解分割数组相关内容，已被999网友关注，涉猎到的知识点内容可以在下方电子书获得。
Java C++题解分割数组
题目要求
思路一：两次遍历
题目的意思也就是左半边数组的最大值小于等于右半边数组的最小值，那么就找这个分界点就好；
- 首先从后向前遍历，找[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& 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 {
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] 找到最终结果节点索引值，将其+1即得答案。 以上就是Java C++题解leetcode915分割数组示例的详细内容，更多关于Java C++题解分割数组的资料请关注码农之家其它相关文章！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;
}
}
C++
class Solution {
public:
int partitionDisjoint(vectorRust
impl Solution {
pub fn partition_disjoint(nums: Vec
