Partition Array Into Disjoint Intervals

915. 分割数组

分析

从右往左预处理出数组 r[i]，表示从位置 i 到末尾的最小值
遍历查找分界点：
- 从左往右遍历，用变量 l 记录当前 left 的最大值
- 每到一个位置，检查 l <= r[i + 1]，如果满足，说明当前划分是合法的，可以返回当前 left 的长度

时间复杂度

时间复杂度 O(n)

空间复杂度

空间复杂度 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution
{
public:
    int partitionDisjoint(vector<int>& nums)
    {
        int n = nums.size();
        std::vector<int> r(n);
        r[n - 1] = nums[n - 1]; // 1. 初始化最右边元素
        for (int i = n - 2; i >= 0; --i)
            r[i] = std::min(nums[i], r[i + 1]); // 2. 预处理右边最小值数组

        int l = INT_MIN;
        for (int i = 0; i + 1 < n; ++i)
        {
            l = std::max(l, nums[i]); // 3. 记录左边最大值
            if (l <= r[i + 1])         // 4. 检查是否满足条件
                return i + 1;
        }
        return 0;
    }
};