图解LeetCode——915. 分割数组（难度：中等）

一、题目

给定一个数组 nums ，将其划分为两个连续子数组 left 和 right， 使得：

• • left 中的每个元素都小于或等于 right 中的每个元素。
• • left 和 right 都是非空的。
• • left 的长度要尽可能小。

在完成这样的分组后返回 left 的 长度 。用例可以保证存在这样的划分方法。

二、示例

2.1> 示例 1：

【输入】nums = [5,0,3,8,6] 【输出】3 【解释】left = [5,0,3]，right = [8,6]

2.2> 示例 2：

【输入】nums = [1,1,1,0,6,12] 【输出】4 【解释】left = [1,1,1,0]，right = [6,12]

提示：

• • 2 <= nums.length <= 10^5
• • 0 <= nums[i] <= 10^6
• • 可以保证至少有一种方法能够按题目所描述的那样对 nums 进行划分。

三、解题思路

根据题目描述，对于数组left，它的第一个成员就是nums[0]，即：下图中的32。然后我们需要遍历nums数组中的每个数字，当发现遍历的这个数字nums[i]大于32的时候，则表示这个数字暂时可能不属于数组left。那么当发现遍历的这个数字nums[i]小于或等于32的时候，则可以判断出这个数字一定是属于数组left的。

那么由于题目中提到，left 中的每个元素都小于或等于 right 中的每个元素，所以我们需要一个变量leftMax来保存数组left中的最大数字，以及下标index，用于划分数组left和数组right。只要发现遍历的数字小于或等于leftMax时，我们就可以通过移动index来划分出新的数组left。当我们遍历完所有的nums数组中的数字之后，index指向的位置就是数组left的最后一个元素的位置。那么数组left的长度就等于index + 1了。具体操作，请见下图所示：

时间复杂度：O(n)，n 表示数组 nums 的长度。

四、代码实现

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