581. 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:
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 <=.

方法0: sort

思路：

找到正确的排序，从左到右开始一一比较找到两边不一样的点，然后求长度。注意如果有违反的两个数字，这个结果一定大于等于2，但如果没有，最后left和right会错过，返回前要判断相对大小。

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        if (nums.empty()) return 0;
        vector<int> copy(nums.begin(), nums.end());
        sort(copy.begin(), copy.end());
        int left = 0, right = nums.size() - 1, n = nums.size();
        while (left < n && nums[left] == copy[left]) left++;
        while (right >= 0 && nums[right] == copy[right]) right--;
        return right - left + 1 > 0 ? right - left + 1 : 0;
    }
};

方法1: monotonic stack

官方题解：https://leetcode.com/problems/shortest-unsorted-continuous-subarray/solution/

思路：

The idea behind this approach is also based on selective sorting. We need to determine the correct position of the minimum and the maximum element in the unsorted subarray to determine the boundaries of the required unsorted subarray.

To do so, in this implementation, we make use of a stackstack. We traverse over the numsnums array starting from the beginning. As we go on facing elements in ascending order(a rising slope), we keep on pushing the elements’ indices over the stackstack. This is done because such elements are in the correct sorted order(as it seems till now). As soon as we encounter a falling slope, i.e. an element nums[j]nums[j] which is smaller than the element on the top of the stackstack, we know that nums[j]nums[j] isn’t at its correct position.

In order to determine the correct position of nums[j]nums[j], we keep on popping the elemnents from the top of the stackstack until we reach the stage where the element(corresponding to the index) on the top of the stackstack is lesser than nums[j]nums[j]. Let’s say the popping stops when the index on stackstack’s top is kk. Now, nums[j]nums[j] has found its correct position. It needs to lie at an index k + 1k+1.

We follow the same process while traversing over the whole array, and determine the value of minimum such kk. This marks the left boundary of the unsorted subarray.

Similarly, to find the right boundary of the unsorted subarray, we traverse over the numsnums array backwards. This time we keep on pushing the elements if we see a falling slope. As soon as we find a rising slope, we trace forwards now and determine the larger element’s correct position. We do so for the complete array and thus, determine the right boundary.

We can look at the figure below for reference. We can observe that the slopes directly indicate the relative ordering. We can also observe that the point bb needs to lie just after index 0 marking the left boundary and the point aa needs to lie just before index 7 marking the right boundary of the unsorted subarray.

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size(), mn = n - 1, mx = 0;
        stack<int> st1, st2;
        for (int i = 0; i < n; i++) {
            while (!st1.empty() && nums[st1.top()] > nums[i]) {
                mn = min(mn, st1.top());
                st1.pop();
            }
            st1.push(i);
        }
        
        for (int i = n - 1; i >= 0; i--) {
             while (!st2.empty() && nums[st2.top()] < nums[i]) {
                 mx = max(mx, st2.top());
                 st2.pop();
             } 
            st2.push(i);
        }
        return mx - mn > 0 ? mx - mn + 1 : 0;  
    }
};