题目链接
题目描述:
给定一个数组 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<int>& nums) {
int n = nums.size();
// 右数组的最小值
vector<int> 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<int>& 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;
}
};