0581. Shortest Unsorted Continuous Subarray
===========================================
题目信息
--------
:题号: 0581
:难度: Medium
:主题: 连续区间、局部排序、全局非递减、最短长度
:原题: `LeetCode 0581 `_
:重点: 只能选择一个连续子数组排序、排序后整个数组必须非递减、返回最短区间长度、已有序时返回 0
题目重述
--------
给定整数数组 ``nums``,选择其中一个连续子数组,将该子数组按非递减顺序排序,而区间外元素保持原位置。寻找能够使整个数组最终变为非递减序列的最短连续子数组,并返回其长度。
若原数组已经按非递减顺序排列,不需要选择任何区间,返回 ``0``。区间必须包含所有会妨碍全局排序的元素,不能选择若干个分散区间。
自建示例
--------
无序区域会向两侧扩展:
.. code-block:: text
输入: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 之前。
数组已经有序:
.. code-block:: text
输入:nums = [1,2,2,4]
输出:0
解释:数组本身已经非递减。
从左右扫描确定需要扩展的边界
----------------------------
从左到右维护已见最大值:若当前值小于它,当前位置一定需要被纳入排序区间,并更新右边界。再从右到左维护已见最小值:若当前值大于它,当前位置一定需要被纳入,并更新左边界。两次扫描后,``[left,right]`` 正好覆盖所有破坏全局有序性的元素。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
int findUnsortedSubarray(std::vector& nums) {
int n = static_cast(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)``。