Shortest Unsorted Continuous Subarray

此题如果排序的话，我们只需要比较最左边一个和排序数组不一样的位置，还有最右边不一样的位置，这个区间就是最短未排序区间了

class Solution(object):
    def findUnsortedSubarray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        tmp = sorted(nums)
        left = -1
        for index, num in enumerate(nums):
            if num != tmp[index]:
                left = index
                break

        n = len(nums)
        right = n
        for i in xrange(n - 1, -1, -1):
            if nums[i] != tmp[i]:
                right = i
                break

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

此题解法很多，这里再写一种O(n)的解法，其实本质上跟排序这个很相近，都是找最边界的未排好序的位置，不过这里利用了单调栈进行一次递增一次递减的栈操作，最后可以得到最左和最右的位置

class Solution(object):
    def findUnsortedSubarray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        stack = []
        left = sys.maxint
        for i in xrange(n):
            while stack and nums[stack[-1]] > nums[i]:
                left = min(left, stack.pop())
            stack.append(i)

        right = -sys.maxint
        stack = []
        for i in xrange(n - 1, -1, -1):
            while stack and nums[stack[-1]] < nums[i]:
                right = max(right, stack.pop())
            stack.append(i)

        return right - left + 1 if left != sys.maxint else 0