描述

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

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

示例

示例1：

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

示例2：

输入：nums = [1,2,3,4]
输出：0

示例3：

输入：nums = [1]
输出：0

提示

  • 1 <= nums.length <= 104
  • -105 <= nums[i] <= 105

解题思路

  • 首先，我们的目标是确定 连续子数组 的边界，即 left 与 right 的坐标。
  • 维护一个递增的单调栈，对于每个数字，如果该数字小于栈顶元素，我们就不断地弹出栈顶元素，直到：
    • 栈为空
    • 或者当前数字大于等于栈顶元素

上述步骤结束后我们还需要做额外的处理：

  • 更新 left 为出栈的最左边的元素
  • 更新最大值 max_value
  • 更新 right 为当前元素坐标
    • 因为在出栈过程中，可能会把 值很大的元素弹出，所以用一个 max_value 变量维护最大值，在 while 循环之后，还要判断当前元素是否小于这个最大值，如果小于，那么当前元素也一定在 连续子数组 中，所以要更新 right 为当前坐标。
    • flag 是为了针对已经是递增的特殊情况。

      代码

      class Solution {
public int findUnsortedSubarray(int[] nums) {
 int n = nums.length;
 int left = Integer.MAX_VALUE;
 int right = 0;
 int max_value = Integer.MIN_VALUE;
 boolean flag = true;
 Deque<Integer> deque = new LinkedList<Integer>();
 for (int i = 0; i < n; i++) {
     while (!deque.isEmpty() && nums[i] < nums[deque.peekLast()]) {
         int poll = deque.pollLast();
         left = Math.min(left, poll);
         max_value = Math.max(max_value, nums[poll]);
         right = i;
         flag = false;
     }
     if (nums[i] < max_value) {
         right = i;
     }
     deque.addLast(i);
 }
 return flag == true ? 0 : right - left + 1;
}
}

      复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)。栈存储数字需要线性的空间。