题目地址: 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 弟弟快看-教程,程序员编程资料站,版权归原作者所有

本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发