Daily Leetcode 915. Partition Array into Disjoint Intervals

https://leetcode.com/problems/partition-array-into-disjoint-intervals/

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:

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

题目分析：

给定一个数组，我们需要找出一个分界点，使得分界点左边的所有元素均小于右边的元素，同时要保证左边元素个数尽可能的少。

我们可以设置一个变量记录当前分割点，在设置两个变量，一个是leftMax，记录分割点左边元素中的最大值；另一个是utlMax，记录已经遍历过的元素中的最大值。在遍历过程中，比较当前元素和leftMax，如果当前元素比leftMax小，说明当前元素也应该被分割到左边较小的集合中，因此就可以将分割点移动到当前元素的位置，并且将leftMax更新为utlMax。

需要注意的是，题目最终需要的是左边集合的长度，因此，最后返回的结果是分割位置+1。

代码：

class Solution(object):
    def partitionDisjoint(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        leftMax = utlMax = A[0]
        cutPos = 0
        
        for i in range(len(A)):
            utlMax = max(utlMax, A[i])
            if (A[i] < leftMax):
                leftMax = utlMax
                cutPos = i
            
        return cutPos + 1