581. 最短无序连续子数组

题目

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
请你找出符合题意的 最短 子数组，并输出它的长度。

思路

如果数组nums 存在无序子数组，则在从左到右遍历数组的过程中会遇到当前元素小于已经遍历过的元素的情况，在从右到左遍历数组的过程中会遇到当前元素大于已经遍历过的元素的情况，即遍历到的元素的大小不符合单调性。由于和单调性有关，因此可以使用单调栈得到最短无序子数组。

单调栈存储数组 nums 的下标。在从左到右遍历数组的过程中，从栈底到栈顶的下标对应的元素单调递增（非严格）；在从右到左遍历数组的过程中，从栈底到栈顶的下标对应的元素单调递减（非严格）。
使用start 和 end 分别表示最短无序子数组的开始下标和结束下标，初始时 start 为数组的长度，end 为−1，即初始值都在数组的下标范围以外。
从左到右遍历数组 nums，当遍历到下标 i 时，进行如下操作：
如果栈不为空且栈顶下标对应的元素大于nums[i]，则栈顶下标位于无序子数组中，将栈顶下标出栈，如果出栈下标小于 start 则用出栈下标更新start 的值，重复该操作直到栈为空或者栈顶下标对应的元素小于等于nums[i]；将 i入栈。遍历结束之后即可得到最短无序子数组的开始下标 start。
从右到左遍历数组 nums，当遍历到下标 i 时，进行如下操作：
如果栈不为空且栈顶下标对应的元素小于nums[i]，则栈顶下标位于无序子数组中，将栈顶下标出栈，如果出栈下标大于end 则用出栈下标更新 end 的值，重复该操作直到栈为空或者栈顶下标对应的元素大于等于nums[i]；将 i入栈。遍历结束之后即可得到最短无序子数组的结束下标 end。
得到最短无序子数组的开始下标start 和结束下标 end 之后，即可计算最短无序子数组的长度：
如果start>end，则在遍历过程中没有更新过 start 和 end，最短无序子数组的长度是 0；
如果 start≤end，则最短无序子数组的下标范围是 [start,end]，长度是 end−start+1。

代码

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int len = nums.length;
        //从左到右遍历（栈顶到栈底：从大到小），找出小于前面元素的坐标start
        //从右向左遍历（栈顶到栈底：从小到大），找出大于后面元素的坐标end
        int start = len,end = -1;
        Deque<Integer> leftStack = new LinkedList<>();
        Deque<Integer> rightStack = new LinkedList<>();
        leftStack.push(0);
        for(int i = 1; i < len; i++){
            while(!leftStack.isEmpty() && nums[i] < nums[leftStack.peek()]){
                start = Math.min(start,leftStack.peek());
                leftStack.pop();
            }
            leftStack.push(i);
        }
        rightStack.push(len-1);
        for(int i = len-2; i >= 0; i--){
            while(!rightStack.isEmpty() && nums[i] > nums[rightStack.peek()]){
                end = Math.max(end,rightStack.peek());
                rightStack.pop();
            }
            rightStack.push(i);
        }
        return start > end ? 0 : end - start + 1;
         
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28