LeetCode_单调栈_中等_581.最短无序连续子数组

淡淡的烟草味﹌ 2023-10-06 22:46 70阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个整数数组 nums，**你需要找出一个连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。**

请你找出符合题意的**最短子数组**，**并输出它的长度。**

**示例 1：**  
输入：nums = \[2,6,4,8,10,9,15\]  
输出：5  
解释：你只需要对 \[6, 4, 8, 10, 9\] 进行升序排序，那么整个表都会变为升序排序。

**示例 2：**  
输入：nums = \[1,2,3,4\]  
输出：0

**示例 3：**  
输入：nums = \[1\]  
输出：0

**提示：**  
1 <= nums.length <= 104  
\-105 <= nums\[i\] <= 105

进阶：你可以设计一个**时间复杂度为 O(n)** 的解决方案吗？

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/shortest-unsorted-continuous-subarray

## 2.思路 ##

（1）排序  
如果不考虑时间复杂度为 O(n) 的限制，可以使用排序的方法找出符合题意的最短子数组，具体步骤如下：  
① 在数组 nums 的基础上深拷贝一个新的数组 newNums，并且对 newNums 进行升序排序；  
② 对比 nums 和 newNums，找出最短子数组的左右起点 left 和 right；  
③ 在输出最短子数组的长度时，需要考虑边界情况，例如数组 nums 中的元素本身就是有序的，例如 nums = \[1,2,3,4\]，按照上面的步骤，可求出 left = 4，right = -1，如果此时直接通过 right - left + 1 来求最短子数组的长度，会得到 -4，显然这是错误的。所以通过分析可知，如果 right - left + 1 <= 0，则说明数组 nums 原本就是有序的，直接返回 0 即可；否则，返回 right - left + 1。

（2）单调栈

（3）一次遍历  
思路参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————排序
    class Solution {
        
    	public int findUnsortedSubarray(int[] nums) {
        
    	    int length = nums.length;
    	    //深拷贝一个新的数组 newNums 
    	    int[] newNums = Arrays.copyOf(nums, length);
    	    //对数组 newNums 进行排序
    	    Arrays.sort(newNums);
    	    int left = 0, right = length - 1;
    	    //对比 nums 和 newNums，找出最短子数组的左右起点 left 和 right
    	    while (left < length && nums[left] == newNums[left]) {
        
    	        left++;
    	    }
    	    while (right >= 0 && nums[right] == newNums[right]) {
        
    	        right--;
    	    }
    	    return Math.max(right - left + 1, 0);
    	}
    }

//思路2————单调栈
    class Solution {
        
    	public int findUnsortedSubarray(int[] nums) {
        
    	    int length = nums.length;
    	    int left = Integer.MAX_VALUE;
    	    int right = Integer.MIN_VALUE;
    	    //单调递增栈，存储元素索引
    	    Stack<Integer> incrStack = new Stack<>();
    	    for (int i = 0; i < length; i++) {
        
    	        while (!incrStack.isEmpty() && nums[incrStack.peek()] > nums[i]) {
        
    	            //栈中弹出的索引所对应的元素是乱序元素，其中最小的索引就是乱序子数组的左边界
    	            left = Math.min(left, incrStack.pop());
    	        }
    	        incrStack.push(i);
    	    }
    	    //单调递减栈，存储元素索引
    	    Stack<Integer> descStack = new Stack<>();
    	    for (int i = length - 1; i >= 0; i--) {
        
    	        while (!descStack.isEmpty() && nums[descStack.peek()] < nums[i]) {
        
    	            //栈中弹出的索引所对应的元素是乱序元素，其中最大的索引就是乱序子数组的右边界
    	            right = Math.max(right, descStack.pop());
    	        }
    	        descStack.push(i);
    	    }
    	    if (left == Integer.MAX_VALUE && right == Integer.MIN_VALUE) {
        
    	        //单调栈没有弹出任何元素，即数组 nums 本来就是有序的
    	        return 0;
    	    } else {
        
    	        return right - left + 1;
    	    }
    	}
    }

//思路3————一次遍历
    class Solution {
        
        public int findUnsortedSubarray(int[] nums) {
        
            int n = nums.length;
            // maxn 为从左往右遍历过程中的遇到的数组 nums 中的最大值
            int maxn = Integer.MIN_VALUE;
            // minn 为从右往左遍历过程中的遇到的数组 nums 中的最小值
            int minn = Integer.MAX_VALUE;
            // left 和 right 分别为最短子数组的左边界下标和右边界下标，初始值均为 -1
            int left = -1;
            int right = -1;
            for (int i = 0; i < n; i++) {
        
                if (maxn > nums[i]) {
        
                    // maxn > nums[i] 说明 nums[maxn...i] 之间肯定不是升序的，将 right 更新为 i  
                    right = i;
                } else {
        
                    //更新 maxn
                    maxn = nums[i];
                }
                if (minn < nums[n - i - 1]) {
        
                    // minn < nums[n - i - 1] 说明 nums[n - i - 1...minn] 之间肯定不是升序的，将 left 更新为 n - i - 1  
                    left = n - i - 1;
                } else {
        
                    //更新 minn
                    minn = nums[n - i - 1];
                }
            }
            return right == -1 ? 0 : right - left + 1;
        }
    }

[Link 1]: https://leetcode.cn/problems/shortest-unsorted-continuous-subarray/solution/zui-duan-wu-xu-lian-xu-zi-shu-zu-by-leet-yhlf/