力扣 915. 分割数组

思路1：两次遍历

可以说是接雨水的简化版。

从右向左遍历数组，得到当前子数组的最小值

再从左向右遍历数组拿到当前子数组最大值的同时，找到满足左连续子数组的所有值小于等于又连续子数组的位置。

解法1

def partitionDisjoint(nums):
    # 两次遍历
    min_right = [0 for _ in range(len(nums))]
    min_right[-1] = nums[-1]
    for i in range(len(nums) - 2, -1, -1):
        min_right[i] = min(min_right[i + 1], nums[i])
    
    max_left = nums[0]
    for i in range(1, len(nums)):
        if max_left <= min_right[i]:
            return i
        else:
            max_left = max(max_left, nums[i])

思路2：一次遍历

只需要维护左连续子数组即可。

cur_max 维护当前左连续子数组的最大值
left_max 维护左连续最短子数组的最大值

解法2

def partitionDisjoint(nums):
    # 一次遍历
    cur_max, left_max, ret = nums[0], nums[0], 0
    for i in range(1, len(nums)):
        cur_max = max(cur_max, nums[i])
        if nums[i] < left_max:
            left_max, ret = cur_max, i
    return ret + 1