0581. Shortest Unsorted Continuous Subarray

题目信息

题号:

0581

难度:

Medium

主题:

连续区间、局部排序、全局非递减、最短长度

原题:

LeetCode 0581

重点:

只能选择一个连续子数组排序、排序后整个数组必须非递减、返回最短区间长度、已有序时返回 0

题目重述

给定整数数组 nums,选择其中一个连续子数组,将该子数组按非递减顺序排序,而区间外元素保持原位置。寻找能够使整个数组最终变为非递减序列的最短连续子数组,并返回其长度。

若原数组已经按非递减顺序排列,不需要选择任何区间,返回 0。区间必须包含所有会妨碍全局排序的元素,不能选择若干个分散区间。

自建示例

无序区域会向两侧扩展:

输入:nums = [1,3,5,4,2,6,7]
输出:4
解释:排序下标 1..4 的 [3,5,4,2] 后,数组变为 [1,2,3,4,5,6,7];更短区间无法把 2 放到 3 和 5 之前。

数组已经有序:

输入:nums = [1,2,2,4]
输出:0
解释:数组本身已经非递减。

从左右扫描确定需要扩展的边界

从左到右维护已见最大值:若当前值小于它,当前位置一定需要被纳入排序区间,并更新右边界。再从右到左维护已见最小值:若当前值大于它,当前位置一定需要被纳入,并更新左边界。两次扫描后,[left,right] 正好覆盖所有破坏全局有序性的元素。

C++ 实现

class Solution {
public:
    int findUnsortedSubarray(std::vector<int>& nums) {
        int n = static_cast<int>(nums.size());
        int left = n;
        int right = -1;
        int maximum = INT_MIN;
        for (int i = 0; i < n; ++i) {
            maximum = std::max(maximum, nums[i]);
            if (nums[i] < maximum) right = i;
        }

        int minimum = INT_MAX;
        for (int i = n - 1; i >= 0; --i) {
            minimum = std::min(minimum, nums[i]);
            if (nums[i] > minimum) left = i;
        }
        return right == -1 ? 0 : right - left + 1;
    }
};

代码分析

左扫描发现的逆序值必须向右延伸到当前位置,右扫描发现的逆序值必须向左延伸;没有任何边界被触发时数组已经有序。两次线性扫描,时间复杂度为 O(n),额外空间复杂度为 O(1)。