博客

581. 最短无序连续子数组

(关键字：

逆序数，单调栈

)

给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

你找到的子数组应是最短的，请输出它的长度。

示例 1:

输入: [2, 6, 4, 8, 10, 9, 15]

输出: 5

解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

说明 :

输入的数组长度范围在 [1, 10,000]。

输入的数组可能包含重复元素 ，所以升序的意思是<=。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

基本思路1:先找出左边不在其正确位置的第一个元素，再找出右边不在其位置的第一个元素，时间复杂度O(n2)。

    int findUnsortedSubarray(vector<int>& nums) {
        int l=0,r=nums.size()-1;
        while(l<nums.size()){
            bool flag=false;
            for(int j=l+1;j<nums.size();j++)
                if(nums[l]>nums[j]){
                    flag=true;
                    break;
                }
            if(flag)
                break;
            else
                l++;
        }
        while(r>=0){
            bool flag=false;
            for(int  i=max(l-1,0);i<=r;i++){
                if(nums[r]<nums[i]){
                    flag=true;
                    break;
                }
            }
            if(flag)
                break;
            else    
                r--;
        }

        return max(r-l+1,0);
        
    }

思路二：既然不在其正确位置，那么必然存在逆序，换而言之，可以找到

逆序

的最大位置和最小位置，但是超时了，其时间复杂度为O(n2)。

    int findUnsortedSubarray(vector<int>& nums) {
        int l=nums.size(),r=0; //注意nums.size()==1的情况
        for(int i=0;i<nums.size()-1;i++)
            for(int j=i+1;j<nums.size();j++){
                if(nums[j]<nums[i]){
                    l=min(l,i);
                    r=max(r,j);
                }
            }

        return max(r-l+1,0);
        
    }

思路三:既然不在正确位置，是不是可以偷懒，先

排序

在比较，时间复杂度O(nlgn),空间O(n)。

    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> orderNum(nums.begin(),nums.end());
        sort(orderNum.begin(),orderNum.end());
        int start=nums.size(),end=-1;
        for(int i=0;i<nums.size();i++){
            if(nums[i]!=orderNum[i]){
                start=i;
                break;
            }
        }
        for(int j=nums.size()-1;j>=0;j--){
            if(nums[j]!=orderNum[j]){
                end=j;
                break;
            }
        }
        return max(0,end-start+1);
        
    }

思路四：何时出现不在正确位置的情况 ，首先出现

逆序

的情形下，所以可以使用

单调栈

,时间O(n),空间O(n);

        int start=nums.size(),end=-1;
        stack<int> stk;
        for(int i=0;i<nums.size();i++){
            while(!stk.empty()&&nums[stk.top()]>nums[i]){
                start=min(start,stk.top());
                stk.pop();
            }
            stk.push(i);
        }
        while(!stk.empty())
            stk.pop();
        for(int j=nums.size()-1;j>=0;j--){
            while(!stk.empty()&&nums[stk.top()]<nums[j]){
                end=max(end,stk.top());
                stk.pop();
            }
            stk.push(j);
        }

        return max(0,end-start+1);
        
    }

思路五：先找到最小，最大逆序数，在逐一比较找到其应该对应的位置。时间复杂度O(n),空间O(1)

    int findUnsortedSubarray(vector<int>& nums) {
        int min_unorderNum=INT_MAX,max_unorderNum=INT_MIN;
        for(int i=0;i<nums.size()-1;i++){
            if(nums[i+1]<nums[i]){
                min_unorderNum=min(min_unorderNum,nums[i+1]);
                max_unorderNum=max(max_unorderNum,nums[i]);
            }
        }
        int start=nums.size(),end=-1;
        for(int i=0;i<nums.size();i++){
            if(min_unorderNum<nums[i]){
                start=i;
                break;
            }
        }
        for(int j=nums.size()-1;j>=0;j--)
            if(max_unorderNum>nums[j]){
                end=j;
                break;
            }

        return max(0,end-start+1);
        
    }