分割数组

难度: Medium

给定一个数组 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 <= 10⁵
0 <= nums[i] <= 10⁶
可以保证至少有一种方法能够按题目所描述的那样对 nums 进行划分。

Submission

运行时间: 76 ms

内存: 0.0 MB

class Solution:
    def partitionDisjoint(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        min_stack = []
        n = len(A)
        for index in range(n-1, 0, -1):
            i = A[index]
            if not min_stack:
                min_stack.append(i)
            else:
                if i <= min_stack[-1]:
                    min_stack.append(i)
                else:
                    min_stack.append(min_stack[-1])
        left_max = A[0]
        for index, i in enumerate(A):
            if i >= left_max:
                left_max = i
            right_min = min_stack.pop()
            if left_max <= right_min:
                return index + 1
        return -1

Explain

此题解采用了两次扫描的方式来解题。首先，从右向左扫描数组A，构建一个min_stack，用来存储每个位置右侧元素的最小值。接着，从左向右扫描数组A，维护一个变量left_max来记录当前位置左侧所有元素的最大值。对于每个位置，如果left_max小于等于当前位置右侧所有元素的最小值（即min_stack的栈顶元素），则意味着左侧数组的最大值不会大于右侧数组的最小值，因此可以在此位置切分数组。返回当前位置加1即得到left数组的长度。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def partitionDisjoint(self, A):
        # 初始化一个栈用来存储从右向左的最小值
        min_stack = []
        n = len(A)
        # 从右向左构建min_stack，存储每个位置右侧的最小值
        for index in range(n-1, 0, -1):
            i = A[index]
            if not min_stack:
                min_stack.append(i)
            else:
                if i <= min_stack[-1]:
                    min_stack.append(i)
                else:
                    min_stack.append(min_stack[-1])
        # left_max用来记录从左向右的最大值
        left_max = A[0]
        # 从左向右遍历寻找分割点
        for index, i in enumerate(A):
            if i >= left_max:
                left_max = i
            right_min = min_stack.pop()
            # 检查当前分割点是否有效
            if left_max <= right_min:
                return index + 1
        return -1

Explore

在构建min_stack的过程中，目的是为了快速获取任意位置右侧的最小值。如果从左向右构建，我们无法提前知道右侧的最小值，因此需要从右向左进行遍历。这样做可以在遍历时直接记录下每个位置右边的最小值，便于后续从左向右遍历时直接使用。

虽然名为min_stack，但实际使用上更类似于一个列表，其主要功能是记录每步的右侧最小值，并不严格遵循后进先出的栈操作原则。在构建min_stack时，我们确保每个位置存储的是从该位置到数组末尾的最小值。在使用时，通过pop操作从后向前依次获取右侧的最小值，这是因为我们在从左向右扫描主数组时需要依次访问这些最小值。

如果当前位置的值小于left_max，这意味着当前元素不会更新left_max的值，left_max保持为之前元素的最大值。这种情况下，left_max依然代表左侧所有元素的最大值。这不会直接影响分割点的寻找，因为分割点的有效性依赖于left_max是否小于等于其右侧的最小值（即min_stack的当前值）。

在构建min_stack时，我们从数组的倒数第二个元素开始到第一个元素结束，为每个位置存储了右侧的最小值。这保证了当我们从左向右遍历数组并逐个pop min_stack时，每个位置都对应一个右侧最小值。由于min_stack的长度与数组长度相匹配（除了数组的最后一个元素），我们可以确保每次pop操作都有元素可供获取。