19.分割数组【LC915】
给定一个数组 nums ，将其划分为两个连续子数组 left 和 right， 使得：
- left 中的每个元素都小于或等于 right 中的每个元素。
- left 和 right 都是非空的。
- left 的长度要尽可能小。
在完成这样的分组后返回 left 的 长度 。
用例可以保证存在这样的划分方法。
补忘记发的Day6
模拟+二次遍历
2022/10/24
- 思路：当左边数组的最大值小于右边数组的最小值时，left 中的每个元素都小于或等于 right 中的每个元素，返回下标+1
- 实现：使用rightMin数组记录该元素右边的数组的最小值（不包括该元素），使用leftMax记录该元素左边的数组的最大值（包括该元素），当leftMax[i]<=rightMin[i]时，返回i+1
- 代码
class Solution { public int partitionDisjoint(int[] nums) { int len = nums.length; int[] leftMax = new int[len];// 记录该元素左边的数组的最大值（包括该元素） int[] rightMin = new int[len];// 记录该元素右边的数组的最小值（不包括该元素） leftMax[0] = nums[0]; rightMin[len-1] = nums[len-1]; for (int i = 1; i < len; i++){ leftMax[i] = Math.max(leftMax[i-1],nums[i]); } for (int i = len-2; i >= 0; i--){ rightMin[i] = Math.min(rightMin[i+1],nums[i+1]); } for (int i = 0; i <len; i++){ if (leftMax[i] <= rightMin[i]){ return i+1; } } return -1; } }
。复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(n)
- 优化
使用leftmax变量代替数组
class Solution { public int partitionDisjoint(int[] nums) { int len = nums.length; int leftMax = 0;// 记录该元素左边的数组的最大值（包括该元素） int[] rightMin = new int[len];// 记录该元素右边的数组的最小值（不包括该元素） rightMin[len-1] = nums[len-1]; for (int i = len-2; i >= 0; i--){ rightMin[i] = Math.min(rightMin[i+1],nums[i+1]); } for (int i = 0; i <len; i++){ leftMax = Math.max(leftMax,nums[i]); if (leftMax <= rightMin[i]){ return i+1; } } return -1; } }
模拟+一次遍历
- 思路：假设一个left的划分，其最大值为maxLeft，划分位置为leftPos，此时nums[0,leftPos]均属于left。
。如果leftPos右侧所有元素都大于等于maxLeft，那么该划分方案合法
。如果在leftPos右侧找到元素nums[i]小于maxLeft，那么该划分方案不合理，此时更新leftPos = i，maxLeft = max(nums[0,i])
- 实现：使用变量curMax维护下标i左边的元素的最大值
class Solution { public int partitionDisjoint(int[] nums) { int n = nums.length; int leftMax = nums[0], leftPos = 0, curMax = nums[0]; for (int i = 1; i < n - 1; i++) { curMax = Math.max(curMax, nums[i]); if (nums[i] < leftMax) { leftMax = curMax; leftPos = i; } } return leftPos + 1; } } 作者：力扣官方题解 链接：https://leetcode.cn/problems/partition-array-into-disjoint-intervals/solutions/1913934/fen-ge-shu-zu-by-leetcode-solution-t4pm/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- 复杂度
。时间复杂度：O(n)
。空间复杂度：O(1)
