【每日一题】最短无序连续子数组

题目描述

---

581. 最短无序连续子数组
给你一个整数数组 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) 的解决方案吗？

题解

---

我们采用从左往右更新右区间，从右往左更新左区间的方式。

如下图1点，它是下降而来，这个时候前面一定有一个更大的值，说明这个值是需要调整的右边界。
如果是水平而来，如2点，就要看先前的max值（max值保存的是前面区间最大的值）与这个值比较，若是比这个值大，说明到这个数为止的区间不满足有序，说明该数是要被调整的右边界；但如果是比这个数小，那就需要更新max值。
如果是上升而来，如3点，实际有两种情况，倘若3这个点是从左到3这个点中最大的，只需要更新max值，但如果比先前最大的小，那么说明3这个点是需要更新的右区间。

最终能够得到需要更新的右区间。左区间的判断也同理。

从上面讲述能够得知，一个点要么是更新区间，要么更新max值！！

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        //if(nums.size() == 1) return 0;
        int r = -2;//是为了后面的 r - l + 1 == 0
        int l = -1; 
        int rnum = INT_MIN;
        int lnum = INT_MAX;
        int n = nums.size();
        for(int i = 0;i < nums.size() ;++i)
        {
            if(rnum > nums[i])
            {//更新右区间
                r = i;
            }
            else
            {//更新值
                rnum = nums[i];
            }
            if(lnum < nums[n - i - 1])
            {//更新左区间
                l = n - i - 1;
            }
            else
            {//更新值
                lnum = nums[n - i - 1];
            }
        }

        return r - l + 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
25
26
27
28
29
30
31
32
33

---

end

• 喜欢就收藏
• 认同就点赞
• 支持就关注
• 疑问就评论