【每日一题】分割数组

题目链接

题目描述：

给定一个数组 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

我们可以先设置一个变量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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17