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
上一篇: java正则表达式使用示例
推荐阅读
-
[easy][Array]581. Shortest Unsorted Continuous Subarray
-
LeetCode 581. Shortest Unsorted Continuous Subarray
-
581. Shortest Unsorted Continuous Subarray
-
581. Shortest Unsorted Continuous Subarray
-
581. Shortest Unsorted Continuous Subarray
-
[LeetCode] 581. Shortest Unsorted Continuous Subarray
-
581. Shortest Unsorted Continuous Subarray
-
581. Shortest Unsorted Continuous Subarray
-
Leetcode0523--Continuous Subarray Sum 连续和倍数
-
LeetCode题解——862.Shortest Subarray with Sum at Least K