LeetCode每日一题系列

题目：915. 分割数组 难度：普通

题目

给定一个数组 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]

提示：

2 <= nums.length <= 105 0 <= nums[i] <= 106 可以保证至少有一种方法能够按题目所描述的那样对 nums 进行划分。

思路

需要记录一个到目前为止的前缀最大值max2以及到目前为止符合要求的分割的前缀的最大值max1，遍历的过程中，假如遍历到值一直不小于max1，那么符合最佳分割的前缀最大值没有必要增大，否则出现了一个小于max1的值，也就是说，此时最少需要把前缀覆盖现在遍历到的下标，所以需要把max1此时对应的坐标和现在的坐标之间的最大值的（max2）更新给max1，才有可能发生前缀max小于等于后边所有值

题解

class Solution:
    def partitionDisjoint(self, nums: List[int]) -> int:
        ans,max1,max2=0,nums[0],nums[0]
        for i in range(1,len(nums)):
            if max1>nums[i]:
                ans,max1=i,max(max1,max2)
            max2=max(max2,nums[i])
        return ans+1