LeetCode_数组_中等_915.分割数组

╰半夏微凉° 2023-10-06 23:46 20阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定一个数组 nums ，将其划分为两个连续子数组 left 和 right， 使得：  
① left 中的每个元素都小于或等于 right 中的每个元素。  
② left 和 right 都是非空的。  
③ left 的长度要尽可能小。  
在完成这样的分组后返回 left 的长度 。

**用例可以保证存在这样的划分方法。**

**示例 1：**  
输入：nums = \[5,0,3,8,6\]  
输出：3  
解释：left = \[5,0,3\]，right = \[8,6\]

**示例 2：**  
输入：nums = \[1,1,1,0,6,12\]  
输出：4  
解释：left = \[1,1,1,0\]，right = \[6,12\]

**提示：**  
2 <= nums.length <= 105  
0 <= nums\[i\] <= 106  
可以保证至少有一种方法能够按题目所描述的那样对 nums 进行划分。

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/partition-array-into-disjoint-intervals

## 2.思路 ##

（1）辅助数组  
要想满足题目中的三个条件，比较容易想到的方法是：  
① 设 left 和 right 中的最大值和最小值分别为 leftMax、rightMin，left 的长度为 res；  
② 从 left = \[nums\[0\]\]，right = \[nums\[1\]…nums\[length - 1\]\] 开始划分，如果 leftMax ≤ rightMin，那么直接返回 res 即可；否则就扩大 left，缩小 right，同时更新 leftMax、rightMin 和 res；  
③ 由于题目保证至少有一种方法能够按题目所描述的那样对 nums 进行划分，所以在划分的过程中一定可以返回 res；

现在的关键是**在划分的过程中如何确定 leftMax、rightMin 和 res 这三者的值**。  
① 对于 res 来说，其初始值肯定为 1，并且 left 每扩大一次（指多加入一个元素），res 就加一；  
② 对于 leftMax 来说，其初始值为 nums\[0\]，当 left 每加入一个元素 nums\[i\] 时，leftMax 更新为 leftMax 和 nums\[i\] 之间的最大值即可；  
③ 对于 rightMin 来说，可以通过**辅助数组**来保存 right（即 nums\[i…length - 1\]，1 ≤ i ≤ length）中的最小值，辅助数组定义如下：

int[] rightMin = new int[length];

在划分之前，我们需要初始化该辅助数组：

Arrays.fill(rightMin, Integer.MAX_VALUE);
    rightMin[length - 1] = nums[length - 1];
    for (int i = length - 2; i >= 1; i--) {
        
        rightMin[i] = Math.min(rightMin[i + 1], nums[i]);
    }

（2）无需辅助数组，一次遍历  
思路参考[该 LeetCode 用户题解][LeetCode]。

① 设 max 表示 nums\[0…i\] 中的最大值，leftMax 表示子数组 left 中的最大值，初始值为 nums\[0\]；  
② 开始遍历 nums，在遍历的过程中先更新 max，然后再判断当前数 nums\[i\] 与 leftMax 的大小：  
1）如果 nums\[i\] < leftMax，那么则需要将 nums\[i\] 划分到 left 中，同时更新 leftMax 和 res；  
2）如果 nums\[i\] ≥ leftMax，那么 nums\[i\] 可以暂时存放到 right 中（该部分无需在代码中体现）；  
③ 遍历结束后，返回 res + 1 即可，需要注意的是这里的 res 保存的是下标而并非长度，所以在返回长度时需要加一。

## 3.代码实现（Java） ##

//思路1————辅助数组
    class Solution {
        
        public int partitionDisjoint(int[] nums) {
        
            int length = nums.length;
            // res 记录 left 的长度，初始值为 1
            int res = 1;
            // leftMax 表示子数组 left 中的最大值
            int leftMax = nums[0];
            // rightMin[i] 表示子数组 right (即 nums[i...length - 1])中的最小值
            int[] rightMin = new int[length];
            //初始化 rightMin
            Arrays.fill(rightMin, Integer.MAX_VALUE);
            rightMin[length - 1] = nums[length - 1];
            for (int i = length - 2; i >= 1; i--) {
        
                rightMin[i] = Math.min(rightMin[i + 1], nums[i]);
            }
            //开始划分
            for (int i = 1; i < length; i++) {
        
                if (leftMax <= rightMin[i]) {
        
                    // left 中的最大值小于等于 right 中的最小值，那么直接返回 res
                    return res;
                } else {
        
                    // 扩大 left，缩小 right，同时更新 leftMax 和 res
                    leftMax = Math.max(leftMax, nums[i]);
                    res++;
                }
            }
            return res;
        }
    }

//思路2————无需辅助数组，一次遍历
    class Solution {
        
        public int partitionDisjoint(int[] nums) {
        
            int length = nums.length;
            int res = 0;
            // max 表示 nums[0...i] 中的最大值
            int max = Math.max(nums[0], nums[1]);
            // leftMax 表示子数组 left 中的最大值
            int leftMax = nums[0];
            for (int i = 0; i < length; i++) {
        
                max = Math.max(max, nums[i]);
                if (nums[i] < leftMax) {
        
                    //如果当前数 nums[i] 小于 leftMax，则需要将其划分到 left 中
                    leftMax = max;
                    //同时更新 res
                    res = i;
                }
            }
            return res + 1;
        }
    }

[LeetCode]: https://leetcode.cn/problems/partition-array-into-disjoint-intervals/solution/yi-ci-bian-li-bu-dong-kan-wo-by-antione/