贪心之最短连续子数组

package com.zhang.reflection.面试.算法模版.贪心算法;


public class 最短无序连续子数组 {
    /**
     * 给定一个整数数组，你需要找出一个连续子数组，将这个子数组升序排列后整个数组都将是升序数组。
     *
     * 请你找出满足题设的最短的子数组。
     * [2,6,4,8,10,9,15]
     * 5
     * 只需对 6,4,8,10,9 排序即可得到升序数组
     *
     * 如果某一个数nums[i]满足大于等于左边的最大值，小于等于右边的最小值，这个数在数组中就是不需要移动位置的。因此可以定出如下的算法流程：
     * 从左往右遍历，如果nums[i]始终是nums[0:i]的最大值，就表示目前为止还是升序。如果碰到了不是最大值的情况，就记录位置，当前遇到了乱序。
     * 从右往左遍历，如果nums[i]始终是nums[i:n-1]的最小值，就表示目前为止还是升序。如果碰到了不是最小值的情况，就记录位置，当前遇到了乱序。
     * 而我们通过下标变换可以一遍循环就完成以上两步，根据步骤1能够得到无序的右边界，根据步骤2可以得到无序的左边界，进一步可以求得无序的长度。
     */
    public int findUnsortedSubarray (int[] nums) {
        // write code here
        int n=nums.length;
        int leftMax=nums[0];
        int rightMin=nums[n-1];
        int l=-1;
        int r=-2;
        for(int i=1;i<n;i++){
            leftMax=Math.max(leftMax,nums[i]);
            rightMin=Math.min(rightMin,nums[n-1-i]);
            if(leftMax!=nums[i]){
                r=i;
            }
            if(rightMin!=nums[n-1-i]){
                l=n-1-i;
            }
        }
        return r-l+1;
    }
}