力扣算法 - 分割數(shù)組

題目

給定一個數(shù)組 A，將其劃分為兩個不相交（沒有公共元素）的連續(xù)子數(shù)組 left 和 right综看，使得：

left 中的每個元素都小于或等于 right 中的每個元素。 left 和 right 都是非空的。 left 要盡可能小。在完成這樣的分組后返回 left 的長度仅仆。可以保證存在這樣的劃分方法垢袱。

示例 1：

輸入：[5,0,3,8,6]
輸出：3
解釋：left = [5,0,3]墓拜，right = [8,6]

示例 2：

輸入：[1,1,1,0,6,12]
輸出：4
解釋：left = [1,1,1,0]，right = [6,12]

思路

從左往右找出所有數(shù)組子集, 對應(yīng)子集的最大值記錄在數(shù)組 maxLeft
從右往做找出反向數(shù)組子集,對應(yīng)子集最小值記錄在數(shù)組 minRight
然后比較 maxLeft[i] 與 minRight[i+1]

例如:
數(shù)組 [5] 所有子集最大值為 5
數(shù)組 [5 ,0] 所有子集最大值為 5
數(shù)組 [5 ,0, 3] 所有子集最大值為 5
數(shù)組 [5 ,0, 3 , 8] 所有子集最大值為 8
數(shù)組 [5 ,0, 3, 8, 6] 所有子集最大值為 5
maxLeft = [ 5, 5, 5, 8, 8]
同理可得 minRight = [0, 0 ,3, 6, 6]
比較時候 maxLeft[0] 與 minRight[1] 相當于是 [5] 在和 [0, 3, 8, 6] 數(shù)組中最大值和最小值進行比較

Swift實現(xiàn)代碼

 func partitionDisjoint(_ A: [Int]) -> Int {
        
        let count = A.count
        
        var maxLeft = [Int](repeating: 0, count: count)
        var minRight = [Int](repeating: 0, count: count)
        
        var firstLeft = A[0]
        var leftIndex = 0
        while leftIndex < count {
            firstLeft = max(firstLeft, A[leftIndex])
            maxLeft[leftIndex] = firstLeft
            leftIndex = leftIndex + 1
        }
        
        var firstRight = A[count-1]
        var rightIndex = count-1
        while rightIndex > 0 {
            firstRight = min(firstRight, A[rightIndex])
            minRight[rightIndex] = firstRight
            rightIndex = rightIndex - 1
        }
        
        var tempIndex = 0
        while tempIndex < count - 1 {
            if maxLeft[tempIndex] <= minRight[tempIndex+1] {
                return tempIndex + 1
            }
            tempIndex = tempIndex + 1
        }
        return 0
    }

Java實現(xiàn)代碼

 public static int partitionDisjoint(int[] A) {
        int N = A.length;
        int[] maxleft = new int[N];
        int[] minRight = new int[N];

        int firstLeft = A[0];
        for (int i = 0; i < N; i++) {
            firstLeft = Math.max(firstLeft, A[i]);
            maxleft[i] = firstLeft;
        }

        int firstRight = A[N-1];
        for (int i = N-1; i > 0; i--) {
            firstRight = Math.min(firstRight, A[i]);
            minRight[i] = firstRight;
        }

        for (int i = 0; i < N -1; i++) {
            if (maxleft[i] <= minRight[i + 1]) {
                return i + 1;
            }
        }
       return 0;
    }

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者