题目地址: https://leetcode.com/problems/partition-array-into-disjoint-intervals/description/
题目描述：
Given an array A, partition it into two (contiguous) subarrays left and right so that:
1、 Everyelementinleftislessthanorequaltoeveryelementinright.；
2、 leftandrightarenon-empty.；
3、 lefthasthesmallestpossiblesize.；
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:
1、 2<=A.length<=30000；
2、 0<=A[i]<=10^6；
3、 ItisguaranteedthereisatleastonewaytopartitionAasdescribed.；
题目大意
找出数组的一个分界点长度，使得这个分界点左边的元素都小于分界点右边的元素。
解题方法
有的题目就是那么烧脑，我现在还是不太能想通没见过的题目。这个题的范围超级大，所以只能用O(N)的算法。
这个题的做法是，我们记录当前已经遍历到的元素最大值和这个元素前面的最大值，如果当前元素比前面已经遇到的最大值更小，说明这个元素一定在左边的划分中（否则前面的最大值会大于这个值），我们的划分要更新到这个元素。
这个做法应该还是挺直观的，理解两个值：当前元素前面的最大值（不包括当前值），到目前元素为止所有值的最大值（包括当前值）。
最坏情况下的时间复杂度是O(N)，空间复杂度是O(1)。
class Solution(object):
def partitionDisjoint(self, A):
"""
:type A: List[int]
:rtype: int
"""
disjoint = 0
v = A[0]
max_so_far = v
for i in range(len(A)):
max_so_far = max(max_so_far, A[i])
if A[i] < v:
v = max_so_far
disjoint = i
return disjoint + 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
参考资料：
https://leetcode.com/problems/partition-array-into-disjoint-intervals/discuss/175904/Explained-Python-simple-O(N)-time-O(1)-space
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发