581. 最短无序连续子数组

题目

方法一：排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> nums_sort = vector<int>(nums);
        sort(nums_sort.begin(), nums_sort.end());
        int l = 0, r = nums.size() - 1;
        while (l < nums.size() && nums[l] == nums_sort[l]) {
            l ++;
        }

        while (r >= 0 && nums[r] == nums_sort[r]) {
            r --;
        }

        return r >= l ? r - l + 1 : 0;
    }
};

时间复杂度：O(n log n)，其中 n 是数组的长度。排序需要 O(n log n) 的时间。

空间复杂度：O(n)，需要额外的数组来存储排序后的结果。

方法二：栈

 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
class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        stack<int> stk;
        int l = n, r = -1;

        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && nums[stk.top()] > nums[i]) {
                l = min(l, stk.top());
                stk.pop();
            }
            stk.push(i);
        }

        stk = stack<int>();

        for (int i = n - 1; i >= 0; --i) {
            while (!stk.empty() && nums[stk.top()] < nums[i]) {
                r = max(r, stk.top());
                stk.pop();
            }
            stk.push(i);
        }

        return r >= l ? r - l + 1 : 0;
    }
};

时间复杂度：O(n)，其中 n 是数组的长度。每个元素最多被压入和弹出栈一次。

空间复杂度：O(n)，栈在最坏情况下可能存储所有元素的索引。