LeetCode581 最短无序连续子数组

发表于 | 分类于 |
字数统计: 396 | 阅读时长 ≈ 1

链接: https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/

题意

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

解法

从前到后考虑整个数组，整个数组由前半部分的递增部分和中间部分的需要进行排序的部分和最后一部分的递增部分组成
设中间部分的起始和结束为start和end，现在就是需要找出start和end的部分
考虑这两个点的特点
对于start，满足start左边的数比其右所有数小
对于end，满足end右边的数比其左边所有数大
从前往后扫描整个数组，维护最大值maxv，如果a[i]大于maxv则进行更新
否则令end=i，这样可以保证end是最后一个满足右边的数都比左边的数大的数
同理，从后往前扫描整个数组，维护最小值minv，如果a[i]小于minv进行更新
否则令start=i，最后一个大于minv的i即为start

代码

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
class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        int start = n, end = n - 1;
        int maxv = nums[0], minv = nums[n - 1];
        for (int i = 1; i < n; i++) {
            if (nums[i] >= maxv) {
                maxv = nums[i];
            }
            else {
                end = i;
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] <= minv) {
                minv = nums[i];
            }
            else {
                start = i;
            }
        }
        // cout << start << ' ' << end << endl;
        return max(0, end - start + 1);

    }
};