581. Shortest Unsorted Continuous Subarray

581. Shortest Unsorted Continuous Subarray

Brute Force(超时)

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int l = nums.size();
        int r = 0;
        for(int i = 0; i < nums.size(); ++i)
        {
            for(int j = i + 1; j < nums.size(); ++j)
            {
                if(nums[j] < nums[i])
                {
                    r = max(r, j);
                    l = min(l, i);
                }
            }
        }
        return l == nums.size() ? 0 : r - l + 1;
    }
};

o(n^2) 每次遍历过程中，当nums[j] < nums[i]，意味着2者都不在其正确位置，若要得到正确排序，需要进行位置的交换，但此处不要求交换，因此将i标记为Unsorted Array的最底端，j标记为Unsorted Array的最顶端

sort

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> numsCopy(nums.begin(), nums.end());
        sort(nums.begin(), nums.end());
        int l = nums.size();
        int r = 0;
        for(int i = 0; i < nums.size(); ++i)
        {
            if(nums[i] != numsCopy[i])
            {
                l = min(i, l);
                r = max(i, r);
            }
        }
        return l == nums.size() ? 0 : r - l + 1;
    }
};

O(nlogn)

排序后比较不同处的两个端点

stack

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        stack<int> s;
        int l = nums.size();
        int r = l;
        for(auto& num : nums)
        {
            while(!s.empty() && num < s.top())
            {
                s.pop();
                l = min(static_cast<int>(s.size()), l);
            }
            s.push(num);
        }
        stack<int> s1;
        for(auto i = nums.end() - 1; i >= nums.begin(); --i)
        {
            while(!s1.empty() && *i > s1.top())
            {
                s1.pop();
                r = min(static_cast<int>(s1.size()), r);
            }
            s1.push(*i);
        }
        return l == nums.size() ? 0 : nums.size() - r - l;
    }
};

T(n):O(n) S(n):O(1)

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int l = nums.size(), r = 0; 
        for(int i = 1; i < nums.size(); ++i)
        {
            int j = i;
            while(j > 0 && nums[i] < nums[j - 1])
            {
                --j;
                l = min(j, l);
            }
        }
        for(int i = nums.size() - 2; i >= 0; --i)
        {
            int j = i;
            while(j < nums.size() - 1 && nums[i] > nums[j + 1])
            {
                ++j;
                r = max(j, r);
            }
        }
        return l == nums.size() ? 0 : r - l + 1;
    }
};

T(n):O(n) S(n):O(1)

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int minNum = INT_MAX, maxNum = INT_MIN;
        for(auto i = nums.begin() + 1; i != nums.end(); ++i)
        {
            if(*i < *(i - 1))
                minNum = min(minNum, *i);
        }
        for(auto i = nums.end() - 2; i >= nums.begin(); --i)
        {
            if(*i > *(i + 1))
                maxNum = max(maxNum, *i);
        }
        int l, r;
        for(l = 0; l < nums.size(); ++l)
        {
            if(nums[l] > minNum)
                break;
        }
        for(r = nums.size() - 1; r >= 0; --r)
        {
            if(nums[r] < maxNum)
                break;
        }
        return minNum == INT_MAX ? 0 : r - l + 1;
    }
};

review

将数组分为三部分NumsA, NumsB, NumsC

其中NumsA和NumsC是有序的，而NumsB是无序的

他们具有如下的规律，NumsA中的所有数字小于NumsB中的最小数字，而NumsC中的所有数字都大于NumsB中的最大数字

转换条件就是NumsB和NumsC中的最小值大于NumsA中的最大值，NumsA和NumsB中的最大值小于NumsC中的最小值

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int right = -1, left = -1;
        int maxn = INT_MIN, minn = INT_MAX;
        int n = nums.size();
        // maxn记录NumsA和NumsB中的最大值，如果这个最大值比后面这个nums[i]大的话，说明不满足NumsA和NumsB中的最大值小于NumsC中的最小值
        // 因此需要更新right为i，表示至少这个i是肯定不满足顺序的
        // 如果都满足，就不断更新maxn为当前最大值，如果后面都是升序，那么right就不会变
        // 因为需要获取左边部分的最大值，所以需要从左向右遍历
        for(int i = 0; i < n; ++i)
        {
            if(maxn > nums[i])
                right = i;
            else
                maxn = nums[i];
        }
        // minn记录NumsB和NumsC中的最小值，如果这个最小值比前面这个nums[i]小的话，说明不满足NumsB和NumsC中的最小值大于NumsA中的最大值
        // 因此需要更新left为i，表示至少这个i是肯定不满足顺序的
        // 如果都满足，就不断更新minn为当前最小值，如果后面都是降序，那么left就不会变
        // 因为需要获取右边部分的最小值，所以需要从右向左遍历
        for(int i = n - 1; i >= 0; --i)
        {
            if(minn < nums[i])
                left = i;
            else
                minn = nums[i];
        }
        return right == -1 ? 0 : right - left + 1;
    }
};