欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

581. Shortest Unsorted Continuous Subarray

程序员文章站 2024-02-24 15:10:00
...

寻找最短的未排序数组。找到未排序数组不难,但是如何寻找最短的?

Approach 1 : Sort

首先对数组进行排序,然后将未排序数组与原数组进行比较
Runtime: 32 ms, faster than 67.07% of C++ online submissions

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> sorted(nums);
        sort(sorted.begin(), sorted.end());
        int n = nums.size(), i = 0, j = n - 1;
        while (i < n && nums[i] == sorted[i])
            i++;
        while (j > i && nums[j] == sorted[j])
            j--;
        return j + 1 - i;
    }
};

Approach 2 : max on left, min on right

Runtime: 24 ms, faster than 98.78% of C++ online submissions

The idea is that:

  1. From the left, for a number to stay untouched, there need to be no number less than it on the right hand side;
  2. From the right, for a number to stay untouched, there need to be no number greater than it on the left hand side;
    Those 2 can be easily checked if we build 2 vectors:
  3. max so far from the left,
  4. and min so far from the right;
/**
 *            /------------\
 * nums:  [2, 6, 4, 8, 10, 9, 15]
 * minr:   2  4  4  8   9  9  15
 *         <--------------------
 * maxl:   2  6  6  8  10 10  15
 *         -------------------->
 */
class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        vector<int> maxlhs(n);   // max number from left to cur
        vector<int> minrhs(n);   // min number from right to cur
        for (int i = n - 1, minr = INT_MAX; i >= 0; i--) minrhs[i] = minr = min(minr, nums[i]);
        for (int i = 0,     maxl = INT_MIN; i < n;  i++) maxlhs[i] = maxl = max(maxl, nums[i]);

        int i = 0, j = n - 1;
        while (i < n && nums[i] <= minrhs[i]) i++;
        while (j > i && nums[j] >= maxlhs[j]) j--;

        return j + 1 - i;
    }
};