Shortest Unsorted Continuous Subarray

这道题要找的是最短的需要重新排序然后使得整个数组重新有序的子数组长度，自己一开始想的是只要用一个很简单的对撞指针就能完成查找，后来就发现对于多个数相等的情况无论指针如何处理都无法得到正确结果，后来就想到实际上可以重新建立一个排序过后的数组再拿来和原数组一一比对找第一个和最后一个不同的位置就是结果了，当然这种方法比较暴力，需要时间复杂度是O(nlgn)，下面是代码

class Solution(object):
    def findUnsortedSubarray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        tmp = sorted(nums)
        n = len(nums)

        left, right = 0, n - 1

        while left < n:
            if nums[left] != tmp[left]:
                break
            left += 1

        while right:
            if nums[right] != tmp[right]:
                break
            right -= 1

        return right - left + 1 if right >= left else 0

看了LeetCode答案之后就发现还有两种方法可以做而且都是O(n)的时间复杂度，这里先列出来思路

• 单调栈，原理是第一个找到的下降的点之前所有的点都是递增的，把它们储存起来放到stack里面直到第一个下坡的点，然后弹出stack元素直到栈顶元素小于这个下坡点，下坡点的坐标减去弹出的个数就是这个数真正应该在的位置，然后用同样方法在右边找一个上坡点，这样两个点真正的位置距离就是最短距离了
• 不用额外空间，需要明确一点即找到的第一个下坡点和第一个上坡点一定是这个未排序数组的最小值和最大值（可以思考一下原因，很直接其实），因此找到这两个点后再拿着这两个点在数组里面比对找到他们应该在的正确位置就行了

可以看出来实际上上述两种做法的思维都是围绕着下坡点必是未排序数组的最小值，上坡点则是最大值来进行的，不同的是第一种用stack辅助找到了真正的位置，而第二种则是通过自己再循环一遍比对找到这个位置