开发者社区> ik1003> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

LeetCode每日一题——915. 分割数组

简介: 给定一个数组 nums ,将其划分为两个连续子数组 left 和 right, 使得: left 中的每个元素都小于或等于 right 中的每个元素。
+关注继续查看

题目

给定一个数组 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 <= 105

0 <= nums[i] <= 106

可以保证至少有一种方法能够按题目所描述的那样对 nums 进行划分。

思路

需要记录一个到目前为止的前缀最大值max2以及到目前为止符合要求的分割的前缀的最大值max1,遍历的过程中,假如遍历到值一直不小于max1,那么符合最佳分割的前缀最大值没有必要增大,否则出现了一个小于max1的值,也就是说,此时最少需要把前缀覆盖现在遍历到的下标,所以需要把max1此时对应的坐标和现在的坐标之间的最大值的(max2)更新给max1,才有可能发生前缀max小于等于后边所有值

题解

class Solution:
    def partitionDisjoint(self, nums: List[int]) -> int:
        ans,max1,max2=0,nums[0],nums[0]
        for i in range(1,len(nums)):
            if max1>nums[i]:
                ans,max1=i,max(max1,max2)
            max2=max(max2,nums[i])
        return ans+1

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
刷爆leetcode第十二期 0026 数组中数字出现的次数
刷爆leetcode第十二期 0026 数组中数字出现的次数
0 0
LeetCode 384. 打乱数组
给你一个整数数组 nums ,设计算法来打乱一个没有重复元素的数组。
0 0
LeetCode 724. 寻找数组的中心下标
给你一个整数数组 nums ,请计算数组的 中心下标 。
0 0
LeetCode 33. 搜索旋转排序数组
整数数组 nums 按升序排列,数组中的值 互不相同 。
0 0
LeetCode 912. 排序数组
给你一个整数数组 nums,请你将该数组升序排列。
0 0
LeetCode 989. 数组形式的整数加法
对于非负整数 X 而言,X 的数组形式是每位数字按从左到右的顺序形成的数组。
0 0
LeetCode 1460. 通过翻转子数组使两个数组相等
给你两个长度相同的整数数组 target 和 arr 。
0 0
LeetCode 1636. 按照频率将数组升序排序
给你一个整数数组 nums ,请你将数组按照每个值的频率 升序 排序。
0 0
LeetCode 1464. 数组中两元素的最大乘积
给你一个整数数组 nums,请你选择数组的两个不同下标 i 和 j,使 (nums[i]-1)*(nums[j]-1) 取得最大值。
0 0
LeetCode 1122. 数组的相对排序
给你两个数组,arr1 和 arr2,arr2 中的元素各不相同 arr2 中的每个元素都出现在 arr1 中 对 arr1 中的元素进行排序,使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。
0 0
+关注
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载
http://www.vxiaotou.com