動機

當初想說只要看到第一個不對的點就可以了，但沒想到的是overlap與根本沒有需要的case…，所以一直出事 [1,2,3,3,3]

Problem

Given an integer array nums, 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.

Return the shortest such subarray and output its length.

 

Example 1:

Input: nums = [2,6,4,8,10,9,15]Output: 5Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Example 2:

Input: nums = [1,2,3,4]Output: 0

Example 3:

Input: nums = [1]Output: 0

 

Constraints:

  • 1 <= nums.length <= 104
  • -105 <= nums[i] <= 105

 

Follow up: Can you solve it in O(n) time complexity?

Sol

  • 從左往右找a[i]>a[j]的最小值 (上升)
  • 從右往左找a[j]<a[i]的最大值 (下降)
  • 在左右兩邊去找要插入的位置
  • 求長度
class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return 0
        a = min([i for i in range(1,len(nums)) if nums[i-1] > nums[i]],key=lambda x: nums[x],default=len(nums)-1)
        b = max([i for i in reversed(range(len(nums)-1)) if nums[i] > nums[i+1]],key=lambda x: nums[x],default=0)
        l = bisect_right(nums[:a],nums[a])
        r = b+bisect_left(nums[b+1:],nums[b])
        return 0 if r - l < 0 else r - l + 1;

case study: stack

一個是單調遞增，一個是單調遞減，可以用stack直接在pop的過程中確定是到哪一個index

public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        Stack < Integer > stack = new Stack < Integer > ();
        int l = nums.length, r = 0;
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i])
                l = Math.min(l, stack.pop());
            stack.push(i);
        }
        stack.clear();
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i])
                r = Math.max(r, stack.pop());
            stack.push(i);
        }
        return r - l > 0 ? r - l + 1 : 0;
    }
}

或是用monotonic stack把要sort的chunk用出來，最後把要合併的chunk合起來

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        stk = []
        for n in nums:
            item = [n,1]
            while stk and (stk[-1][0] > n):
                m, cnt = stk.pop()
                item = [max(item[0],m), cnt+item[1]]
            stk += item,
        a,b = 0,len(stk)-1
        while a<len(stk) and stk[a][1] == 1:
            a += 1
        while 0<=b and stk[b][1] == 1:
            b -= 1
        #print(stk)
        return sum([seg[1] for seg in stk[a:b+1]], 0)