题目

原题在此
Given an integer array nums, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order.
Return the shortest such subarray and output its length.

Example 1:
Input: nums = [2,6,4,8,10,9,15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Example 2:
Input: nums = [1,2,3,4]
Output: 0

Example 3:
Input: nums = [1]
Output: 0

Constraints:

1 <= nums.length <= $10^4$
$-10^5$ <= nums[i] <= $10^5$

Follow up: Can you solve it in O(n) time complexity?

解析

从左侧开始向右找到第一次值变小的点, 记做left;
从右侧开始想做找到第一次值变大的点, 记做right;
在[left:right]区间内找到最大值和最小值, 记做min,max; (中间的这一坨里面可能会有比[begin:left]区间里的值小的或比[right:end]区间里大的.)
在[:left]区间内找到min的上界, 既从begin起至left内第一个比min大的位置;
在[right:]区间内找到max的下界, 既从right起至end内第一个大于等于max的位置;
比较上下界的距离.
这些std函数都是$O(N)$的所以整体复杂度也是$O(N)$.

代码

c++

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while(left < right && nums[left] <= nums[left + 1]) left++;
        while(right > left && nums[right - 1] <= nums[right]) right--;
        auto [min_it, max_it] = minmax_element(nums.begin() + left, nums.begin() + right + 1);
        auto left_cut = upper_bound(nums.begin(), nums.begin() + left, *min_it);
        auto right_cut = lower_bound(nums.begin() + right, nums.end(), *max_it);
        return distance(left_cut, right_cut);
    }
};