# 0581. Shortest Unsorted Continuous Subarray
###### tags: `Leetcode` `Medium` `Stack` `Greedy` `Sorting`
Link: https://leetcode.com/problems/shortest-unsorted-continuous-subarray/
## 思路
### 思路一 $O(N)$ $O(1)$
非常直觉的解法
首先先找递减序列确定边界 [minIdx, maxIdx]，因为递减序列无论如何都会要包含在要sort的subarray里面
然后找到这个subarray里面的最大和最小值 [minVal, maxVal]
再从[0, minIdx)里面找看有没有大于minVal的值，如果有左边界变成那个idx
再从(maxIdx, nums.length)里面倒序找看有没有小于maxVal的值，如果有有边界变成那个idx

### 思路二 $O(N)$ $O(1)$
更简单的思路 速度也更快
简单来说 对于每一个元素都要看前面有没有元素比它大，后面有没有元素比它小
所以遍历两次
第一次正序 一直记录前面的最大值 如果最大值比现在元素大，就要记录位置
第二次倒序 一直记录前面的最小值 如果最小值比现在元素小，就要记录位置

### 思路三 stack $O(N)$ $O(N)$
## Code
### 思路一

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int minIdx = Integer.MAX_VALUE;
        int maxIdx = Integer.MIN_VALUE;
        
        for(int i = 0;i < nums.length-1;i++){
            if(nums[i] > nums[i+1]){
                minIdx = Math.min(minIdx, i);
                maxIdx = Math.max(maxIdx, i+1);
            }
        }
        
        if(minIdx == Integer.MAX_VALUE) return 0;
        
        int minVal = Integer.MAX_VALUE;
        int maxVal = Integer.MIN_VALUE;
        for(int i = minIdx;i <= maxIdx;i++){
            minVal = Math.min(minVal, nums[i]);
            maxVal = Math.max(maxVal, nums[i]);
        }
        
        int l=minIdx, r=maxIdx;
        for(int i = 0;i < minIdx;i++){
            if(nums[i] > minVal){
                l = i;
                break;
            }
        }
        for(int i = nums.length-1;i > maxIdx;i--){
            if(nums[i] < maxVal){
                r = i;
                break;
            }
        }
        return r-l+1;
    }
}

### 思路二

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int right = 0, max = nums[0];
        int left = n-1, min = nums[n-1];
        for(int i=0; i<n; i++){
            if(nums[i]<max) right = i;
            else max = nums[i];
        }
        for(int i=n-1; i>=0; i--){
            if(nums[i]>min) left = i;
            else min = nums[i];
        }
        return right>left?right-left+1:0;
    }
}

### 思路三

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        int left = nums.length-1;
        for(int i = 0;i < nums.length;i++){
            while(!stack.isEmpty() && nums[stack.peek()]>nums[i]){
                left = Math.min(left, stack.pop());
            }
            stack.push(i);
        }
        int right = 0;
        stack = new Stack<>();
        for(int i = nums.length-1;i >= 0;i--){
            while(!stack.isEmpty() && nums[stack.peek()]<nums[i]){
                right = Math.max(right, stack.pop());
            }
            stack.push(i);
        }
        if(left<right) return right-left+1;
        else return 0;
    }
}