写点什么

【LeetCode】分割数组 Java 题解

作者:Albert
  • 2022-10-24
    北京
  • 本文字数: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; }}
复制代码

总结

  • 上述算法的时间复杂度是 O(n),空间复杂度是 O(n)

  • 今天的算法题目需要一定的思考深度,才能顺利解决,建议多做几次,加深理解。

  • 坚持算法每日一题,加油!我会继续更新,也欢迎算法爱好者一起交流学习。

发布于: 刚刚阅读数: 3
用户头像

Albert

关注

还未添加个人签名 2019-09-29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】分割数组Java题解_算法_Albert_InfoQ写作社区