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^5
  • 0 <= nums[i] <= 10^6
  • 对于给定的输入，至少存在一个有效答案

解题思路

这道题要求找到一个分割点，使得左边部分的所有元素都小于等于右边部分的所有元素。

核心思路是：左边部分的最大值 ≤ 右边部分的最小值

有两种主要解法：

方法一：双数组预处理（推荐）

  • 预处理出每个位置左边的最大值数组 maxLeft
  • 预处理出每个位置右边的最小值数组 minRight
  • 从左到右扫描，找到第一个满足 maxLeft[i] <= minRight[i+1] 的位置

方法二：贪心算法

  • 维护当前左边部分的最大值 maxLeft
  • 当遇到比 maxLeft 小的元素时，说明可能需要扩展左边部分
  • 记录当前位置作为候选分割点

方法一的时间复杂度为 O(n)，空间复杂度为 O(n)，思路清晰易理解。方法二虽然空间复杂度更优，但逻辑稍复杂。本解答采用方法一。

代码实现

class Solution {
public:
    int partitionDisjoint(vector<int>& nums) {
        int n = nums.size();
        vector<int> maxLeft(n), minRight(n);
        
        // 构建左侧最大值数组
        maxLeft[0] = nums[0];
        for (int i = 1; i < n; i++) {
            maxLeft[i] = max(maxLeft[i-1], nums[i]);
        }
        
        // 构建右侧最小值数组
        minRight[n-1] = nums[n-1];
        for (int i = n-2; i >= 0; i--) {
            minRight[i] = min(minRight[i+1], nums[i]);
        }
        
        // 找到第一个满足条件的分割点
        for (int i = 0; i < n-1; i++) {
            if (maxLeft[i] <= minRight[i+1]) {
                return i + 1;
            }
        }
        
        return n - 1;
    }
};

class Solution:
    def partitionDisjoint(self, nums: List[int]) -> int:
        n = len(nums)
        max_left = [0] * n
        min_right = [0] * n
        
        # 构建左侧最大值数组
        max_left[0] = nums[0]
        for i in range(1, n):
            max_left[i] = max(max_left[i-1], nums[i])
        
        # 构建右侧最小值数组
        min_right[n-1] = nums[n-1]
        for i in range(n-2, -1, -1):
            min_right[i] = min(min_right[i+1], nums[i])
        
        # 找到第一个满足条件的分割点
        for i in range(n-1):
            if max_left[i] <= min_right[i+1]:
                return i + 1
        
        return n - 1

public class Solution {
    public int PartitionDisjoint(int[] nums) {
        int n = nums.Length;
        int[] maxLeft = new int[n];
        int[] minRight = new int[n];
        
        // 构建左侧最大值数组
        maxLeft[0] = nums[0];
        for (int i = 1; i < n; i++) {
            maxLeft[i] = Math.Max(maxLeft[i-1], nums[i]);
        }
        
        // 构建右侧最小值数组
        minRight[n-1] = nums[n-1];
        for (int i = n-2; i >= 0; i--) {
            minRight[i] = Math.Min(minRight[i+1], nums[i]);
        }
        
        // 找到第一个满足条件的分割点
        for (int i = 0; i < n-1; i++) {
            if (maxLeft[i] <= minRight[i+1]) {
                return i + 1;
            }
        }
        
        return n - 1;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var partitionDisjoint = function(nums) {
    const n = nums.length;
    const maxLeft = new Array(n);
    const minRight = new Array(n);
    
    // 构建左侧最大值数组
    maxLeft[0] = nums[0];
    for (let i = 1; i < n; i++) {
        maxLeft[i] = Math.max(maxLeft[i-1], nums[i]);
    }
    
    // 构建右侧最小值数组
    minRight[n-1] = nums[n-1];
    for (let i = n-2; i >= 0; i--) {
        minRight[i] = Math.min(minRight[i+1], nums[i]);
    }
    
    // 找到第一个满足条件的分割点
    for (let i = 0; i < n-1; i++) {
        if (maxLeft[i] <= minRight[i+1]) {
            return i + 1;
        }
    }
    
    return n - 1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)
空间复杂度O(n)

相关题目