Leetcode #581 Shortest Unsorted Continuous Subarray – 陪你刷題

今天要來探討的是 Leetcode 581 Shortest Unsorted Continuous Subarray

方法 0 暴力解

input = [ 1, 2, 10, 11, 6, 8]

陣列必須是遞增的，所以若有元素是比他前面的元素還要小的話，代表這兩個元素需要互換位置。以上面例子來說， input[2] < input[4] ，這兩個就形成了一個 unsorted subarry ，所以我們將所有元素倆倆比較，找出最小與最大的區間邊界，即可決定 unsorted subarray 。

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

Time Complexity O($n^2$)

Space Complexity O(1)

方法 1 Sorting

透過 sorting 可以知道每個元素應該在的位置，可以比較第一個和最後一個不一致的 index ，這兩個 index 合起來即為 unsorted 區間。

[ 1, 2, 4, 7, 10, 11, 7, 12, 6, 18, 19]

[ 1, 2, 4, 6, 7, 7, 10, 11, 12, 18, 19]

一比較你就知道 unsorted 區間為 index 3 ~ index 8 。

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> sort_nums(nums.begin(), nums.end());
        std::sort (sort_nums.begin(), sort_nums.end());
        int left = nums.size(), right = -1;
        for (int i=0; i<nums.size();i++) {
            if (sort_nums[i] != nums[i]) {
                left = std::min(left, i);
                right = i;
            }
        }
        if (left == nums.size()) return 0;
        else return right-left+1;
    }
};

Time Complexity O (n logn)

Space Complexity O (n)

方法 2 Monotonic Stack

這個方法用的是 monotonic stack 的概念，我在之前有寫過一篇文章探討過 Monotonic Stack – 陪你刷題，透過 monotonic stack 來找出 unsorted subarray 的左邊界跟右邊界， monotonic stack 讓 stack 內的元素都維持遞稱或是遞減，一旦違反這個單調性，就需要把 stack 內的元素 pop 直到符合單調性，每次的 pop 都是在幫助元素找出他應該在的位置上，這個動作也決定了 unosrted subarray 的邊界。

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int left = nums.size()-1, right = 0; 

        stack<int> st;
                // Find left boundary
        for (int i=0; i<nums.size(); i++)
        {
            while (!st.empty() && nums[st.top()] > nums[i])
            {
                left = min (left, st.top());
                st.pop();
            }
            st.push (i);
        }
        while (!st.empty())
        {
            st.pop();
        }
        // Find right boundary
        for (int i=nums.size()-1; i>=0; i--)
        {
            while (!st.empty() && nums[st.top()] < nums[i])
            {
                right = max(right, st.top());
                st.pop();
            }
            st.push (i);
        }

        return right-left>0 ? right-left+1:0;
    }
};

Time Complexity O(n)

Space Complexity O(n)