大家好，扬哥的一个朋友最近向扬哥哭诉：输在了阿里的最后一面的算法题上。究竟是什么难题？今天我们一起来看看，这道算法题，应该怎么解。

题目

给定一个数组 nums，将其划分为两个连续子数组 left 和 right，使得：

left 中的每个元素都小于或等于 right 中的每个元素。

left 和 right 都是非空的。

left 的长度要尽可能小。

示例 1：

输入：nums = [5,0,3,8,6]
输出：3
解释：left = [5,0,3]，right = [8,6]

示例 2：

输入：nums = [1,1,1,0,6,12]
输出：4
解释：left = [1,1,1,0]，right = [6,12]

解题步骤

算法代码

private int getSplitIdx(int[] nums){
    int pos = -1;
    int[] minBs = new int[nums.length];
    minBs[nums.length-1] = nums[nums.length-1];
    //从右到左查找，当前数值跟后面数值对比，取小的数值
    for(int i=nums.length-2; i>=0; i--){
        if(minBs[i+1]>nums[i]){
            minBs[i] = nums[i];
        }else{
            minBs[i] = minBs[i+1];
        }
    }
    printArray("过度数组:   ", minBs, true);
    //从左往右查找
    int max = nums[0];
    for(int i=1; i<minBs.length; i++){
        //如果nums[i]<max 继续往后找
        if(nums[i]<max){
            continue;
        }
        //如果过度数组大于前面所有的数据，返回下标
        if(minBs[i]>max){
            return i;
        }else{//否则更新最大值
            max = nums[i];
        }
    }
    return pos;
}

算法思路

从右往左找最小值，存储在过渡数组中。如果数组当前值比后面的值大，则保留后面小的值为当前值，即从右往左找最小值。

从左往后找最大值，初始max为数组的第一个元素，如果max小于过渡数据对应的值，则找到临界点，否则将数组的当前值，赋值给max。

验证代码一

@Test
public void testArraySplitByCompare(){
    System.out.println("数组拆分为left和right两部分，使左边的任意一个数字都小于右边的任意一个数字");
    int nums[] = new int[]{5,0,3,8,6};
    printArray("输入数组:   ", nums, true);
    int pos = getSplitIdx(nums);
    if(pos>-1){
        System.out.println("输出位置:   " + pos);
        printArray("具体解释:   left = ", Arrays.copyOfRange(nums, 0, pos), false);
        printArray(", right = ", Arrays.copyOfRange(nums, pos, nums.length), true);
    }else{
        System.out.println("Error ...");
    }
}

private void printArray(String preParam, int[] bs, boolean fin){
    System.out.print(preParam+Arrays.toString(bs));
    if(fin){
        System.out.println();
    }
}

输出结果一

数组拆分为left和right两部分，使左边的任意一个数字都小于右边的任意一个数字
输入数组:   [5, 0, 3, 8, 6]
过渡数组:   [0, 0, 3, 6, 6]
输出位置:   3
具体解释:   left = [5, 0, 3], right = [8, 6]

进程已结束，退出代码 0

将 int nums[] = new int[]{5,0,3,8,6}; 替换为 int nums[] = new int[]{1,1,1,0,6,12}

验证代码二

@Test
    public void testArraySplitByCompare(){
        System.out.println("数组拆分为left和right两部分，使左边的任意一个数字都小于右边的任意一个数字");
        int nums[] = new int[]{1,1,1,0,6,12};
        printArray("输入数组:   ", nums, true);
        int pos = getSplitIdx(nums);
        if(pos>-1){
            System.out.println("输出位置:   " + pos);
            printArray("具体解释:   left = ", Arrays.copyOfRange(nums, 0, pos), false);
            printArray(", right = ", Arrays.copyOfRange(nums, pos, nums.length), true);
        }else{
            System.out.println("Error ...");
        }
    }

输出结果二

数组拆分为left和right两部分，使左边的任意一个数字都小于右边的任意一个数字
输入数组:   [1, 1, 1, 0, 6, 12]
过渡数组:   [0, 0, 0, 0, 6, 12]
输出位置:   4
具体解释:   left = [1, 1, 1, 0], right = [6, 12]

进程已结束，退出代码 0