Shortest Unsorted Continuous Subarray

发表于 | 分类于 | 浏览 次

Given an integer array, 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, too.

You need to find the shortest such subarray and output its length.

Example 1:

1
2
3
Input: [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.

Note:

  1. Then length of the input array is in range [1, 10,000].
  2. The input array may contain duplicates, so ascending order here means <=.

解法1:暴力破解

假设数组nums长度为n。
考虑每一个可能的子数组nums[i:j]，要使得nums[i:j]是最长的未排序子数组，需要满足以下条件：
nums[0:i-1]是有序的，nums[j+1:n-1]是有序的。nums[i:j]是无序的，且nums[i:j]中的最小值大于nums[i-1]，nums[i:j]中的最大值小于nums[j+1]。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int res = nums.size();
        for(int i=0;i<nums.size();i++){
            for(int j=i;j<nums.size();j++){
                int min_val = 2147483647;
                int max_val = -2147483648;
                int prev = - 2147483648;
                for(int k=i;k<j;k++){
                    min_val = min_val > nums[k]? nums[k]:min_left;
                    max_val = max_val > nums[k]? max_val:nums[k];
                }
                // min_val为nums[i:j]中的最小值，max_val为nums[i:j]中的最大值
                //nums[0:i]或者nums[j+1:]不满足有序
                if((i>0 && nums[i-1] > min_val) || (j <nums.size() && nums[j] < max_val)){
                    continue;
                }
                int k = 0;
                //nums[0:i]是有序的 
                //若能成立则运行完后prev=nums[i-1]
                while(k < i && prev <= nums[k]){
                    prev = nums[k];
                    k++;
                }
                if(k!=i)
                    continue;
                k = j;
                //nums[j:]是有序的且nums[j] >= nums[i-1]
                while(k < nums.size() && prev<=nums[k]){
                    prev = nums[k];
                    k++;
                }
                // 思考一下：为什么要小于呢？
                if(k==nums.size()){
                    res = res > j - i ? j - i:res;
                }
            }
        }
        return res;
    }
};

解法2：较好一点的暴力破解

如果对于nums[i]来说，其前面的数都小于等于它，后面的数都大于等于它，则它的位置是正确的，否则它的位置是错误的。一对相距最远的数的位置就是我们要找的。
遍历数组，每次遇到逆序的数就更新左边界和右边界。左边界取较小的，右边界取较大的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int l = nums.size(), r = 0; // l是左边界，r是右边界，左边界取较小的，右边界取较大的  
        for(int i=0;i<nums.size()-1;i++){
            for(int j=i+1;j<nums.size();j++){
                if(nums[j] < nums[i]){
                    r = r > j? r : j;
                    l = l < i? l : i;
                }
            }
        }
        return r - l < 0?0:r - l + 1;
    }
};

时间复杂度为O(n2)。

解法3：使用栈

和解法2的思路一样都是不断更新左边界和左边界。

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
class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        stack<int> st;
        int l = nums.size(), r = 0;
        for(int i=0;i<nums.size();i++){
            while(!st.empty() && nums[st.top()] > nums[i]){
                l = l > st.top()? st.top():l;
                st.pop();
            }
            st.push(i);
        }
        while(!st.empty()){
            st.pop();
        }
        for(int i=nums.size()-1;i>=0;i--){
            while(!st.empty() && nums[st.top()] < nums[i]){
                r = r > st.top()?r:st.top();
                st.pop();
            }
            st.push(i);
        }
        return r - l ? r - l + 1: 0;
    }
};

时间复杂度为O(n)，空间复杂度为O(n)。

解法4：两次遍历

两次遍历，分别找左边界和右边界。
左边界是位置最左，且逆序的数，右边界是位置最右且逆序的数。
一个数若大于其后任意一个数就可以判断该数是逆序的。因此，一个数若大于其后最小的一个数既可以看做是逆序的。
同样，一个数若小于其前面任意一个数即可认定该数是逆序。因此，一个数若小于其前面最大的一个数即可认定该数是逆序的。

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
29
class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        if(nums.size()<2){
            return 0;
        }
        int leftmost = -1, rightmost = -1;
        int min_right = nums[nums.size()-1];
        int max_left = nums[0];
        for(int i=nums.size()-2;i>=0;i--){
            if(nums[i] > min_right){
                leftmost = i;
            }else{
                min_right = nums[i];
            }
        }
        if(leftmost == -1){
            return 0;
        }
        for(int i=1;i<nums.size();i++){
            if(nums[i] < max_left){
                rightmost = i;
            }else{
                max_left = nums[i];
            }
        }
        return rightmost - leftmost + 1;
    }
};

时间复杂度为O(n)，空间复杂度为O(1)。