欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 581. Shortest Unsorted Continuous Subarray

程序员文章站 2024-02-24 15:22:55
...

题目

给定一个整数数组,你需要寻找一个连续的子数组,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。

你找到的子数组应是最短的,请输出它的长度。

示例 1:

输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序,那么整个表都会变为升序排序。

说明 :

输入的数组长度范围在 [1, 10,000]。
输入的数组可能包含重复元素 ,所以升序的意思是<=。

思路

题解给出了五个思路,分别是超级暴力求解法、暴力求解法、排序法、堆栈法和不用额外空间的方法,其时间和空间复杂度依次降低。我个人想到的是排序法,排序法的思路很简单,排个序然后两个列表进行比较,就能找到字串长度。
堆栈法的思路是这样:
因为nums一开始也是递增的,那么先压栈,直到第一个递减的数出现,然后pop栈,直到找到这个数应该所在的位置k。依此类推,直到找到最小的k,最大值也同理,找到最大的l,然后做差就行。
不要额外空间的最优解法是这样:
因为把这个列表画成上上下下的图,画个图会很好理解。他的思路是先遍历一遍,找到所有下降的地方即局部极大值,然后找到这些局部极大值中的最大值max。同理,找到所有局部极小值,然后得到这些局部极小值的最小值min,那么,我们要在列表开始单调递增的区间里找到那个比min还小的那个数,在倒序访问列表单调递减的里面找到比最大值max还大的那个数。这两个找到的数就是这个字串的上下界(字串里没有这俩数)。

代码

这里仅贴上第五种最优方法的代码:

class Solution(object):
    def findUnsortedSubarray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) < 2: return 0
        
        l, r = 0, len(nums) - 1
        
        while l < len(nums) - 1 and nums[l] <= nums[l + 1]:
            l += 1
        
        while r > 0 and nums[r] >= nums[r -1]:
            r -= 1
            
        if l > r:
            return 0
            
        temp = nums[l:r+1]
        tempMin = min(temp)
        tempMax = max(temp)
        
        while l > 0 and tempMin < nums[l-1]:
            l -= 1
        
        while r < len(nums) - 1 and tempMax > nums[r+1]:
            r += 1
            
        return r - l + 1