分割数组

问题简述

给定整数数组 nums，将其划分为 left 和 right 两部分，要求：
    1. left 中的每个元素都小于或等于 right 中的每个元素；
    2. left 的长度要尽可能小。
返回 left 的长度，题目保证 left 和 right 都非空；

要求：
    时间复杂度 O(n)
    空间复杂度 O(n) 或 O(1)

915. 分割数组 - 力扣（LeetCode）

思路1

• 记 lmax[i] 表示 nums[:i] 中的最大值，rmin[i] 表示 nums[i:] 中的最小值；

• 返回使 lmax[i - 1] <= rmin[i] 的最小 i；

  这里要 <=，否则意味着所有相同的最小值会被分到 left，不符合题意；

Python

class Solution:
    def partitionDisjoint(self, nums: List[int]) -> int:
        
        n = len(nums)

        # 计算 lmax
        lmax = [float('-inf')] * n
        lmax[0] = nums[0]
        for i in range(1, n):
            lmax[i] = max(lmax[i - 1], nums[i])
        
        # 计算 rmin
        rmin = [float('inf')] * n
        for i in range(n - 2, -1, -1):
            rmin[i] = min(rmin[i + 1], nums[i])
        
        for i in range(1, n):
            if lmax[i - 1] <= rmin[i]:  # 注意这里要 <=；如果是 <，意味着所有相同的最小值会分到 left，不符合题意
                return i
        
        return -1

优化：计算 lmax 和比较的过程都是顺序遍历，可以合并到一起，节省部分空间；

Python：优化1

class Solution:
    def partitionDisjoint(self, nums: List[int]) -> int:
        
        n = len(nums)
        rmin = [float('inf')] * n
        for i in range(n - 2, -1, -1):
            rmin[i] = min(rmin[i + 1], nums[i])
        
        # 合并计算 lmax 和比较过程
        lmax = nums[0]
        for i in range(1, n):
            if lmax <= rmin[i]:
                return i
            lmax = max(lmax, nums[i])
        
        return -1

思路2

【贪心法】 - 分割数组 - qwf

时间复杂度 O(n)，空间复杂度 O(1)

• 使用 lmax 记录已划分 left 中的最大值；

  • 根据题意，left 的中至少会存在一个元素，因此可以初始化 lmax=nums[0]；

• 使用 amax 记录遍历过程中的最大值；

• 当 nums[i] < lmax 时，说明需要扩充 left，即需要把 i 之前的所有元素都添加到 left；同时更新 lmax=amax；

以 nums=[3,4,1,5,6] 为例，下面是：

初始化：
    amax = 3
    lmax = 3
    ret = 1

for i in range(1, len(nums)):

    i  amax  lmax  ret
    1  3     3     1
    2  4     3     1
    3  5     4     3
    4  6     4     3

返回：
    ret = 3

Python

class Solution:
    def partitionDisjoint(self, nums: List[int]) -> int:

        lmax = amax = nums[0]
        ret = 1
        for i in range(1, len(nums)):
            amax = max(amax, nums[i])
            if nums[i] < lmax:
                ret = i + 1
                lmax = amax
        
        return ret