LeetCode_ Monotone stack_ Medium_ 581. shortest unordered continuous subarray

1. subject

Give you an array of integers nums , You need to find a contiguous subarray , If you sort this subarray in ascending order , Then the whole array will be sorted in ascending order .

Please find the one that matches the meaning of the question Shortest subarray , And output its length .

Example 1：
Input ：nums = [2,6,4,8,10,9,15]
Output ：5
explain ： You just need to be right [6, 4, 8, 10, 9] Sort in ascending order , Then the whole table will be sorted in ascending order .

Example 2：
Input ：nums = [1,2,3,4]
Output ：0

Example 3：
Input ：nums = [1]
Output ：0

Tips ：
1 <= nums.length <= 10⁴
-10⁵ <= nums[i] <= 10⁵

Advanced ： You can design a The time complexity is O(n) Is there a better solution ？

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/shortest-unsorted-continuous-subarray

2. Ideas

（1） Sort
If the time complexity is not considered, it is O(n) The limitation of , You can use the sorting method to find the shortest subarray that matches the meaning of the question , The specific steps are as follows ：
① In the array nums Deep copy a new array based on newNums, And right newNums Sort in ascending order ;
② contrast nums and newNums, Find the left and right starting points of the shortest subarray left and right;
③ When outputting the length of the shortest subarray , Boundary conditions need to be considered , For example, an array of nums The elements in are themselves ordered , for example nums = [1,2,3,4], Follow the steps above , It can be found that left = 4,right = -1, If you go directly through right - left + 1 To find the length of the shortest subarray , You'll get -4, It's obviously wrong . So through the analysis, we can know , If right - left + 1 <= 0, Then the array nums It was ordered , Go straight back to 0 that will do ; otherwise , return right - left + 1.

（2） Monotonic stack

3. Code implementation （Java）

// Ideas 1———— Sort 
public int findUnsortedSubarray(int[] nums) {
    
    int length = nums.length;
    // Deep copy a new array  newNums 
    int[] newNums = Arrays.copyOf(nums, length);
    // An array  newNums  Sort 
    Arrays.sort(newNums);
    int left = 0, right = length - 1;
    // contrast  nums  and  newNums, Find the left and right starting points of the shortest subarray  left  and  right
    while (left < length && nums[left] == newNums[left]) {
    
        left++;
    }
    while (right >= 0 && nums[right] == newNums[right]) {
    
        right--;
    }
    return right - left + 1 <= 0 ? 0 : right - left + 1;
}

// Ideas 2———— Monotonic stack 
public int findUnsortedSubarray(int[] nums) {
    
    int length = nums.length;
    int left = Integer.MAX_VALUE;
    int right = Integer.MIN_VALUE;
    // Monotonically increasing stacks , Storage element index 
    Stack<Integer> incrStack = new Stack<>();
    for (int i = 0; i < length; i++) {
    
        while (!incrStack.isEmpty() && nums[incrStack.peek()] > nums[i]) {
    
            // The elements corresponding to the index popped up in the stack are out of order elements , The smallest index is the left boundary of the out of order subarray 
            left = Math.min(left, incrStack.pop());
        }
        incrStack.push(i);
    }
    // Monotonically decreasing stacks , Storage element index 
    Stack<Integer> descStack = new Stack<>();
    for (int i = length - 1; i >= 0; i--) {
    
        while (!descStack.isEmpty() && nums[descStack.peek()] < nums[i]) {
    
            // The elements corresponding to the index popped up in the stack are out of order elements , The largest index is the right boundary of the out of order subarray 
            right = Math.max(right, descStack.pop());
        }
        descStack.push(i);
    }
    if (left == Integer.MAX_VALUE && right == Integer.MIN_VALUE) {
    
        // The monotone stack doesn't pop up any elements , It's an array  nums  It's orderly 
        return 0;
    } else {
    
        return right - left + 1;
    }
}