难度: Medium
原题连接
内容描述
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: 3
Explanation: left = [5,0,3], right = [8,6]
Example 2:
Input: [1,1,1,0,6,12]
Output: 4
Explanation: left = [1,1,1,0], right = [6,12]
Note:
2 <= A.length <= 30000
0 <= A[i] <= 10^6
It is guaranteed there is at least one way to partition A as described.
思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******
用前缀最大数组与后缀最大数组做，满足要求的临界点是前半部分的最大值刚好由大于变成了小于等于后半部分的最小值
class Solution(object):
def partitionDisjoint(self, A):
"""
:type A: List[int]
:rtype: int
"""
if not A or len(A) == 0:
return 0
max_num, min_num = A[0], A[-1]
max_prefix, min_suffix = [max_num], [min_num]
for i in range(1, len(A)):
max_num = max(A[i], max_num)
max_prefix.append(max_num)
for i in range(len(A)-2, -1, -1):
min_num = min(A[i], min_num)
min_suffix.insert(0, min_num)
idx = 0
while max_prefix[idx] > min_suffix[idx+1]:
idx += 1
return idx + 1