[LeetCode] 581、最短无序连续子数组

题目描述

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

<=

）。你找到的子数组应是最短的，请输出它的长度。（可能有重复元素）

示例：

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

解题思路

做出来容易，优化不容易。

• 简单思路，排序：我们将数组

  nums

  进行排序，记为

  nums_sorted

  。然后我们比较

  nums

  和

  nums_sorted

  的元素来决定最左边和最右边不匹配的元素。它们之间的子数组就是要求的最短无序子数组。 O ( n l o g n ) + O ( n ) O(nlogn) + O(n) O(nlogn)+O(n)
• 两次遍历：从前往后，记录下遍历过的值里面的最大值；从后往前遍历，记录下遍历过的值里面的最小值。
  • 从前往后：如果

    nums[i] < tmpMax

    ，就将右边界更新为

    i

    ，否则更新

    tmpMax

    。
  • 从后往前：如果

    nums[i] > tmpMin

    ，就将左边界更新为

    i

    ，否则更新

    tmpMin

    。
  最终：

  return right - left + 1 > 0? right - left + 1: 0;

参考代码

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int length = nums.size();
        if(length <= 1)
            return 0;
        
        int right = 0, left = length - 1;
        int tmpMax = INT_MIN, tmpMin = INT_MAX;
        for(int i = 0; i < length; i++){
            if(nums[i] < tmpMax)
                right = i;
            else
                tmpMax = nums[i];
        }
        for(int i = length-1; i >= 0; i--){
            if(nums[i] > tmpMin)
                left = i;
            else
                tmpMin = nums[i];
        }
        
        return right - left + 1 > 0? right - left + 1: 0;
    }
};