算法刷题目数组和矩阵
Source
Edit
History

需要排序的最短子数组的长度

需要排序的最短子数组的长度

一、题目

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

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

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

Leetcode：https://leetcode.cn/problems/shortest-unsorted-continuous-subarray

二、思路

先从右边向左遍历，有一个标志 left 先赋值为 -1，同时记录最小值，如果遇到了比最小值大的元素，则将此下标赋给 left，否则就更新最小值。一直到遍历完整个数组。那么此时找到了最左边应该排序的位置。因为这个位置的元素比数组中最小的元素还要大。

当从右往左遍历完之后，left 如果为 -1，则说明此数组本身是有序的，直接返回 0 即可。如果 left 不为 -1，则接着从左边向右边遍历

有一个标志 right ，同时记录最大值。从左向右遍历的过程中，如果遇到了比最大值小的元素，则将此下标赋给 right，否则就更新最大值。一直到遍历完整个数组。那么此时找到了最右边应该排序的位置。因为这个位置的元素比数组中最大的元素还要小。

如果第一步得到的 left 不为 -1，则一定可以找到 right，因为此数组是无序的。

最终返回 right - left + 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
34
35
36
37
38
39
40
41
42
43
44
#include <vector>
#include <iostream>

class Solution {
public:
    int findUnsortedSubarray(const std::vector<int>& nums) {
        if (nums.empty() || nums.size() < 2) {
            return 0;
        }
        int count = nums.size();
        int left = -1;
        int min = count-1;
        for (int i = count-2; i >= 0; --i) {
            if (nums[i] > nums[min]) {
                left = i;
            } else {
                min = i;
            }
        }
        if (left == -1) {
            return 0;
        }
        int right = 0;
        int max = 0;
        for (int i = 1; i < count; ++i) {
            if (nums[i] < nums[max]) {
                right = i;
            } else {
                max = i;
            }
        }
        return right - left + 1;
    }
};

int main() {
    Solution s;
    // std::vector<int> arr{1, 5, 3, 4, 2, 6, 7};
    std::vector<int> arr{2, 6, 4, 8, 10, 9, 15};
    // std::vector<int> arr{2, 1};
    auto res = s.findUnsortedSubarray(arr);
    std::cout << res << std::endl;
    return 0;
}