[leetcode] 915. Partition Array into Disjoint Intervals

[leetcode] 915. Partition Array into Disjoint Intervals

Description

Given an array A, partition it into two (contiguous) subarrays left and right so that:

Every element in left is less than or equal to every element in right.left and right are non-empty.left has the smallest possible size.Return the length of left after such a partitioning. It is guaranteed that such a partitioning exists.Example 1:

Input: [5,0,3,8,6]Output: 3Explanation: left = [5,0,3], right = [8,6]

Example 2:

Input: [1,1,1,0,6,12]Output: 4Explanation: left = [1,1,1,0], right = [6,12]

Note:

2 <= A.length <= 300000 <= A[i] <= 10^6It is guaranteed there is at least one way to partition A as described.

分析

题目的意思是：这道题要把一个list分成两个连续的list，第一个list的所有的值都不大于第二个list，还要保证第一个list的长度最小。 我是左思右想也没想到用两个数据就搞定了，left数组就存储A[0:i]的最大值，right数据就存储A[i:]的最小值，从左到右遍历如果left[i-1]<=right[i]，说明已经找到了满足条件的i，学习一下

代码

class Solution: def partitionDisjoint(self, A: List[int]) -> int: N=len(A) maxleft=[None]*N minright=[None]*N m=A[0] for i in range(N): m=max(m,A[i]) maxleft[i]=m m=A[-1] for i in range(N-1,-1,-1): m=min(m,A[i]) minright[i]=m for i in range(1,N): if(maxleft[i-1]<=minright[i]): return i

参考文献

​​[LeetCode]Approach 1: Next Array​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。