LeetCode: 581. Shortest Unsorted Continuous Subarray

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

581. Shortest Unsorted Continuous Subarray

LeetCode - Shortest Unsorted Continuous Subarray

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.

Example 1:

Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Note:

Then length of the input array is in range [1, 10,000].
The input array may contain duplicates, so ascending order here means ⇐.

解题分析

第一种办法就是对数组进行排序，然后跟原数组进行对比，看看那个元素变化了。

第二种办法就是从两边找逆序的小和大，然后再从两段寻找需要调整的元素。

思考题

再推敲一下从两段两段夹逼的阶梯方法。

参考资料

最短无序连续子数组 - 最短无序连续子数组 - 力扣（LeetCode）

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.

Example 1:

Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Note:

Then length of the input array is in range [1, 10,000].
The input array may contain duplicates, so ascending order here means ⇐.

 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
29
30
31
32
33
34
35
36
37
38
39
/**
 * Runtime: 4 ms, faster than 60.88% of Java online submissions for Shortest Unsorted Continuous Subarray.
 * Memory Usage: 51.8 MB, less than 7.69% of Java online submissions for Shortest Unsorted Continuous Subarray.
 */
public int findUnsortedSubarray(int[] nums) {
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    boolean flag = false;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i - 1] > nums[i]) {
            flag = true;
        }
        if (flag) {
            min = Math.min(min, nums[i]);
        }
    }
    flag = false;
    for (int i = nums.length - 2; i >= 0; i--) {
        if (nums[i] > nums[i + 1]) {
            flag = true;
        }
        if (flag) {
            max = Math.max(max, nums[i]);
        }
    }
    int left, right;
    for (left = 0; left < nums.length; left++) {
        if (min < nums[left]) {
            break;
        }
    }
    for (right = nums.length - 1; right >= 0; right--) {
        if (max > nums[right]) {
            break;
        }
    }
    return right - left < 0 ? 0 : right - left + 1;
}