Leetcode 581 Shortest Unsorted Continuous Subarray

发表于 |

给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
你找到的子数组应是最短的，请输出它的长度。

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

说明 :

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

分析：

  1. 我们需要找一段最短无序数组nums[start:end]，使其排序完成后整个数组也是有序的，换个角度想，我们也可以找两段最长的有序数组nums[:start]和nums[end:]，那么怎样找到“最长”的情况呢
  2. 对于某一个元素nums[i]，如果其满足nums[i] < min(nums[i+1:])，则我们可以说nums[i]是处于有序序列中的，即nums[:start]中。
  3. 对于某一个元素nums[j]，如果其满足nums[j] > max(nums[:j])，则我们可以说nums[j]也是处于有序序列中的，即nums[end:]中。

思路：

  1. 从0开始，找到第一个不满足nums[i] < min(nums[i+1:])的i，记为start
  2. 从len(nums)-1开始，找到第一个不满足nums[j] > max(nums[:j])的j，记为end
  3. 用s[i]记录min(nums[i:])，用l[j]记录max(nums[:j])
  4. 处理数组初始有序情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution(object):
    def findUnsortedSubarray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        s = [nums[-1]] * len(nums)
        l = [nums[0]] * len(nums)
        start = end = 0
        # 找到start
        for i in range(len(nums)-2,-1,-1):
            s[i] = min(nums[i], s[i+1])
        for i in range(len(nums)-1):
            if nums[i] > s[i+1]:
                start = i;break
        # 找到end
        for i in range(1,len(nums)):
            l[i] = max(l[i-1],nums[i])
        for i in range(len(nums)-1,0,-1):
            if nums[i] < l[i-1]:
                end = i;break
        # 处理初始有序情况
        if start == end == 0: return 0
        return end - start + 1

307 / 307 test cases passed.
difficulty: easy
Runtime: 72 ms,beats 29%