题解 | #最短无序连续子数组#

import java.util.*;

/**
 * NC209 最短无序连续子数组
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int findUnsortedSubarray (int[] nums) {
        return solution1(nums);
        // return solution2(nums);
        // return solution3(nums);
        // return solution4(nums);
    }

    /**
     * 单调栈+贪心
     * @param nums
     * @return
     */
    private int solution1(int[] nums){
        int n = nums.length;

        // 方式1
        Stack<Integer> leftStack = new Stack<>();
        Stack<Integer> rightStack = new Stack<>();
        // 方式2
        // Deque<Integer> leftStack = new ArrayDeque<>();
        // Deque<Integer> rightStack = new ArrayDeque<>();
        // 方式3
        // Deque<Integer> leftStack = new LinkedList<>();
        // Deque<Integer> rightStack = new LinkedList<>();

        int left = Integer.MAX_VALUE;
        int right = 0;
        for(int i=0; i<n; i++){
            // 单调栈(单调增) 从左往右
            while(!leftStack.isEmpty() && nums[leftStack.peek()]>nums[i]){
                // 贪心
                left = Math.min(left, leftStack.pop());
            }
            leftStack.push(i);

            // 单调栈(单调减) 从右往左
            while(!rightStack.isEmpty() && nums[rightStack.peek()]<nums[n-i-1]){
                // 贪心
                right = Math.max(right, rightStack.pop());
            }
            rightStack.push(n-i-1);
        }

        return left==Integer.MAX_VALUE?0:right-left+1;
    }

    /**
     * 单调栈+贪心
     * @param nums
     * @return
     */
    private int solution2(int[] nums){
        int n = nums.length;

        Deque<Integer> leftStack = new ArrayDeque<>();
        Deque<Integer> rightStack = new ArrayDeque<>();

        int left = Integer.MAX_VALUE;
        int right = 0;
        for(int i=0; i<n; i++){
            // 单调栈(单调增) 从左往右
            while(!leftStack.isEmpty() && nums[leftStack.peekFirst()]>nums[i]){
                // 贪心
                left = Math.min(left, leftStack.pollFirst());
            }
            leftStack.offerFirst(i);

            // 单调栈(单调减) 从右往左
            while(!rightStack.isEmpty() && nums[rightStack.peekFirst()]<nums[n-i-1]){
                // 贪心
                right = Math.max(right, rightStack.pollFirst());
            }
            rightStack.offerFirst(n-i-1);
        }

        return left==Integer.MAX_VALUE?0:right-left+1;
    }

    /**
     * 单调栈+贪心
     * @param nums
     * @return
     */
    private int solution3(int[] nums){
        int n = nums.length;

        Deque<Integer> leftStack = new LinkedList<>();
        Deque<Integer> rightStack = new LinkedList<>();

        int left = Integer.MAX_VALUE;
        int right = 0;
        for(int i=0; i<n; i++){
            // 单调栈(单调增) 从左往右
            while(!leftStack.isEmpty() && nums[leftStack.peekLast()]>nums[i]){
                // 贪心
                left = Math.min(left, leftStack.pollLast());
            }
            leftStack.offerLast(i);

            // 单调栈(单调减) 从右往左
            while(!rightStack.isEmpty() && nums[rightStack.peekLast()]<nums[n-i-1]){
                // 贪心
                right = Math.max(right, rightStack.pollLast());
            }
            rightStack.offerLast(n-i-1);
        }

        return left==Integer.MAX_VALUE?0:right-left+1;
    }

    /**
     * 双指针+贪心
     * @param nums
     * @return
     */
    private int solution4(int[] nums){
        int n = nums.length;

        int left = Integer.MAX_VALUE;
        int right = 0;
        int min = nums[n-1];
        int max = nums[0];
        for(int i=1; i<n; i++){
            // min(nums[n-i-1,n-1])
            min = Math.min(min, nums[n-i-1]);
            // max(nums[0,i])
            max = Math.max(max, nums[i]);
            // 贪心 从右往左
            if(nums[n-i-1] != min){
                left = n-i-1;
            }
            // 贪心 从左往右
            if(nums[i] != max){
                right = i;
            }
        }

        return left==Integer.MAX_VALUE?0:right-left+1;
    }
}