最短无序连续子数组

题目链接

最短无序连续子数组

题目描述

注意点

• 找出符合题意的 最短 子数组，并输出它的长度
• -100000 <= nums[i] <= 100000

解答思路

• 本题的数组可以分为三段，左段中段和右段，如下图所示

• 观察规律可知，左段元素始终比中段小，右段元素始终比中段大，区别是中段中的元素不是严格递增的，所以关键是要找到中段的左右边界
• 将中段的左右边界分别定义为begin和end，进行两次遍历
  • 从左到右维护一个最大值max，在进入右段之前，那么遍历到的nums[i]都是小于max的，end也就是遍历中最后一个小于max元素的位置（进入右端后新的元素始终都比之前维护的max大）
  • 从右到左维护一个最小值min，在进入左段之前，那么遍历到的nums[i]也都是大于min的，begin也就是最后一个大于min元素的位置（进入左端后新的元素始终都比之前维护的min小）

代码

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int maxValue = Integer.MIN_VALUE;
        int minValue = Integer.MAX_VALUE;
        int begin = 0;
        int end = -1;
        for (int i = 0; i < n; i++) {
            if (nums[i] < maxValue) {
                end = i;
            } else {
                maxValue = nums[i];
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            if (nums[i] > minValue) {
                begin = i;
            } else {
                minValue = nums[i];
            }        
        }
        return end - begin + 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

关键点

• 双指针的思想
• 怎么找到中段的左右边界