力扣算法 - 分割数组

题目

给定一个数组 A，将其划分为两个不相交（没有公共元素）的连续子数组 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]

思路

• 从左往右找出所有数组子集, 对应子集的最大值 记录在数组 maxLeft
• 从右往做找出反向数组子集,对应子集最小值 记录在数组 minRight
• 然后比较 maxLeft[i] 与 minRight[i+1]

例如:
数组 [5] 所有子集最大值为 5
数组 [5 ,0] 所有子集最大值为 5
数组 [5 ,0, 3] 所有子集最大值为 5
数组 [5 ,0, 3 , 8] 所有子集最大值为 8
数组 [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] 数组中最大值和最小值进行比较

Swift实现代码

 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实现代码

 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;
    }