分割数组

• 两次遍历
• 一次遍历（优化空间复杂度）

题目链接

题目描述：

给定一个数组 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]

思路分析：

两次遍历

题目要我们left 中的每个元素都小于或等于 right 中的每个元素，我们可以理解为left中最大的元素小于等于right中最小的元素。
怎么知道right中的最小值？
可以采用反向遍历的方法：创建个等大的MinRight数组，先放置最后一个元素，遍历判断当前i位置的nums的元素是否小于MinRight[i + 1]位置的元素。如图：

当minRight数组安置完后：

此时我们定义一个MaxLeft变量，用来记录left范围的最大值，遍历数组当我们发现MaxLeft <= MinRight[i + 1]时，就可以返回i + 1（长度）了。因为MinRight[i + 1]代表了i + 1位置及以后的最小值。

代码如下：

class Solution {
public:int partitionDisjoint(vector& nums) {int n = nums.size();// 右数组的最小值vector MinRight(n);MinRight[n - 1] = nums[n - 1];for (int i = n - 2; i >= 0; i--){MinRight[i] = min(MinRight[i + 1], nums[i]);}int MaxLeft = MinRight[0];for (int i = 0; i < n - 1; i++){MaxLeft = max(MaxLeft, nums[i]);if (MaxLeft <= MinRight[i + 1]){return i + 1;}}// 题目保证有return n - 1;}
};

一次遍历（优化空间复杂度）

我们可以先设置一个变量pos来划分left和right区间，然后用LeftMax来记录left区间的最大值，向后遍历动态改变pos和LeftMax：后边遇比LeftMax小的元素就把pos移过去，这个时候有可能在中途就出现了比LeftMax更大的元素，所以还需要定义CurMax来记录出现过的最大的元素。

代码如下：

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