题目描述
给一个数组nums,需要把他换分为两个连续的子数组,要求是两个子数组非空,且左边的每个元素都小于等于右边每个元素,左边数组长度尽可能小
求left的长度
f1-模拟+2次遍历 |
基本分析
- 题目直白的翻译是啥?能不能找到一个靠左的点,让左子数组的最大值<=右子数组的最小值?
- 怎么知道靠右边区间的最小值的情况?直接1次遍历,记录在数组minv中,其中minv[i]表示从i到n-1的子数组最小值
- 怎么拿到结果?从左到右再次遍历,用一个值维护遇到的最大值maxv,如果遍历到i出的最大值是maxv,有maxv<=minv[i+1],就找到个这个长度i+1
代码
class Solution:
def partitionDisjoint(self, nums: List[int]) -> int:
n = len(nums)
minv = [0] * (n+10)
minv[n-1] = nums[n-1]
for i in range(n-2, -1, -1):
minv[i] = min(minv[i+1], nums[i])
maxv = 0
for i in range(n):
maxv = max(maxv, nums[i])
if maxv <= minv[i+1]:
return i+1
return -1
复杂度
时间:\(O(n)\)
空间:\(O(n)\)
总结
- 能看到是求两个区间的最值,区间是可变化的
- 维护从右到左的最小值用遍历实现,先赋n-1处的初值,再两两对比就行
- 再次从左到右遍历时候,不再需要数组,用一个值maxv实现就行。