Daily LeetCode – day0087 0915. Partition Array into Disjoint Intervals

// 0915. Partition Array into Disjoint Intervals
class Solution {
    public int partitionDisjoint(int[] nums) {
        int n = nums.length;
        int leftMax = nums[0];
        int alternate = nums[0];
        int bound = 0;
        for (int i = 1; i < n; ++i) {
            if (nums[i] < leftMax) {
                leftMax = alternate;
                bound = i;
            } else {
                alternate = Math.max(alternate, nums[i]);
            }
        }
        return bound + 1;
    }
}

学习笔记：
这是一道中等难度的题目，不过还是有点困难的。
要保证左边比右边的每一个元素小。
只需要三个变量其实就可以维护住了：左边最大值、备胎值、左边界。
遇到比左边的大的，那么就需要更新备胎值，暂时不把他放进来。
遇到比左边最大值小的，那肯定要把小数字吸收进来，所以之前遇到的备胎必须转正了。
遇到相等怎么办呢？得好好考虑，应该题目说要让左半尽可能元素少。那么相等就不应该放进来。
最终要注意，求的是元素个数，所以我们算的bound边界需要加1才是答案。