581. 最短无序连续子数组

题目描述

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

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

解题思路

子数组相关的题目常常与贪心、分治、动态规划等联系起来。但这道题目比较非典型，它没有体现出“子结构特征”：意思是一个数组的乱序性与它的子数组的乱序性并没有太大关联，顺序的数组在前后扩展之后也可能变成乱序，整体的乱序性也不会保证局部的乱序性。实际上，乱序子数组只与边界元素有关，只要边界元素是乱序的，那么整个子数组都是乱序的。只要一想到“边界”的概念，双指针法就呼之欲出了。

这道题目实际上可以分成两个步骤：先找到数组中乱序的部分，然后再把乱序的部分重新排列到合适的位置，最终答案取决于重排后的新位置的边界。

找数组中乱序的部分

找乱序子数组是比较难的，但反过来想，找顺序子数组是很简单的，那么乱序子数组就是数组中“不顺序”的部分。

顺着这条思路，在乱序子数组存在的情况下，我们可以假设数组在区间 [0, left] 上是顺序递增的，在 [right, ) 上也是顺序递增的，子数组 [left, right] 就是我们所假设的乱序子数组。注意，边界情况 right - left < 1 是没有意义的，子数组一定要有递减的边界，长度至少是2。

重排乱序子数组

本题并不需要我们把整个乱序子数组重新排列，而只要求重排后的新位置的边界（前后边界长度之差即为长度），因此我们只需要关心乱序子数组中最小值/最大值在新数组中的位置。因此本题到这里变成了一个选择排序的问题，遍历一遍原数组，找到最小值/最大值的合适的位置。这里的遍历相当于两头的选择排序，从左到右遍历，找到第一个比最小值大的元素，即为最小值的新位置，从右到左遍历，找到第一个比最大值小的元素，即为最大值的新位置。

以上算法都可以很方便地通过维护 minIndex 和 maxIndex 两个下标完成。

另一种解法

从另一个角度看，把目光焦点放在数组中有序的部分，那么这道题的单调栈特点就非常明显了：从左到右维护一个升序单调栈，一旦遇到递减元素，就不断弹出栈顶元素，假设弹栈后栈顶剩余元素下标为 k ，那么递减元素的新下标就是 k+1 ，我们可以记录 k+1 的最小值，即为乱序数组的左边界。同理，从右到左也可以找到右边界。

单调栈解法的缺点是维护栈需要 O(N) 的空间开销，不如双指针法。

复杂度分析

时间复杂度 = 双指针遍历数组 = O(N)
空间复杂度 = 维护双指针 = O(1)

知识点

数组，子数组，双指针，单调栈

代码

  1. class Solution {
  2. public:
  3.     int findUnsortedSubarray(vector<int>& nums) {
  4.         int n = nums.size();
  5.         int left = 0, right = n - 1;
  6.         while ((left + 1) < n && nums[left] <= nums[left + 1]) {
  7.             ++left;
  8.         }
  9.         while ((right - 1) >= 0 && nums[right - 1] <= nums[right]) {
  10.             --right;
  11.         }
  12.         if (right - left < 1) {
  13.             return 0;
  14.         }
  15.         int minValue = numeric_limits<int>::max();
  16.         int maxValue = numeric_limits<int>::min();
  17.         for (int i = left; i <= right; ++i) {
  18.             if (nums[i] < minValue) {
  19.                 minValue = nums[i];
  20.             }
  21.             if (nums[i] > maxValue) {
  22.                 maxValue = nums[i];
  23.             }
  24.         }
  25.         int minIndex = 0, maxIndex = 0;
  26.         for (int i = 0; i < n; ++i) {
  27.             if (nums[i] > minValue) {
  28.                 minIndex = i;
  29.                 break;
  30.             }
  31.         }
  32.         for (int i = n - 1; i >= 0; --i) {
  33.             if (nums[i] < maxValue) {
  34.                 maxIndex = i;
  35.                 break;
  36.             }
  37.         }
  38.         return maxIndex - minIndex + 1;
  39.     }
  40. };

参考资料

  1. 最短无序连续子数组 Leetcode官方题解