【LeetCode】分割数组 Java 题解

作者：Albert

2022-11-12
北京
本文字数：936 字
阅读完需：约 3 分钟

题目描述

给定一个数组 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]
链接：https://leetcode.cn/problems/partition-array-into-disjoint-intervals/description/

复制代码

思路分析

今天的算法题目是数组题目。题目要求我们将 nums 划分成 left, right 两个连续的子数组，且满足 left 中的每个元素都小于或等于 right 中的每个元素，left 的长度尽可能短。我们首先可以采用模拟的方法解决这个题目，双重循环，固定枚举 left, right，判断是否满足题目的要求。
使用朴素算法，中间有比较多的重复计算。我们再次分析题目，left 中的每个元素都小于或等于 right 中的每个元素，等价于 left 中的最大值小于等于 right 中的最小值。我们定义一个 minRight, 从右向左遍历，计算出每个位置的 right 最小值。minRight 计算完成之后，我们从左向右计算 left 的最大值 maxLeft, 由于 left 需要去最短，我们找到第一个 maxLeft <= minRight[i + 1]的时候，即为答案。具体实现代码如下，供参考。

通过代码

class Solution {    public int partitionDisjoint(int[] nums) {        int n = nums.length;        int[] minRight = new int[n];        minRight[n - 1] = nums[n - 1];        for (int i = n - 2; i >= 0; i--) {            minRight[i] = Math.min(nums[i], minRight[i + 1]);        }
        int maxLeft = 0;        for (int i = 0; i < n - 1; i++) {            maxLeft = Math.max(maxLeft, nums[i]);            if (maxLeft <= minRight[i + 1]) {                return i + 1;            }        }        return n - 1;    }}