leetcode
leetcode 501 ~ 550
最短无序连续子数组

最短无序连续子数组

难度:

标签:

题目描述

代码结果

运行时间: 24 ms, 内存: 17.4 MB


/*
 * 思路:
 * 我们可以使用Java Stream API来简化代码。
 * 首先将数组转换为Stream,并排序。然后将排序后的Stream转换回数组。
 * 接下来,使用IntStream找到第一个和最后一个不相等的元素的索引。
 * 最后计算需要排序的子数组长度。
 */
 
import java.util.*;
import java.util.stream.*;
 
public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int[] sorted = Arrays.stream(nums).sorted().toArray();
        int left = IntStream.range(0, nums.length).filter(i -> nums[i] != sorted[i]).findFirst().orElse(-1);
        int right = IntStream.range(0, nums.length).map(i -> nums.length - 1 - i).filter(i -> nums[i] != sorted[i]).findFirst().orElse(-1);
        return (left == -1) ? 0 : right - left + 1;
    }
}

解释

方法:

该题解的思路是先找到最短无序连续子数组的候选区间 [l, r],然后再扩展该区间直到满足条件。具体步骤如下: 1. 从左到右扫描数组,找到第一个破坏升序的位置 l; 2. 从右到左扫描数组,找到最后一个破坏升序的位置 r; 3. 如果没找到 l 和 r,说明数组本身有序,直接返回 0; 4. 在 [l, r] 区间内找到最小值 Min 和最大值 Max; 5. 从 l 开始向左扩展,直到找到第一个小于 Min 的位置,更新 l; 6. 从 r 开始向右扩展,直到找到第一个大于 Max 的位置,更新 r; 7. 返回 r - l + 1 作为最短无序连续子数组的长度。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在第一步寻找破坏升序的位置时,为什么选择从左到右扫描数组,这种方法有没有考虑到所有可能的破坏升序的情况?
从左到右扫描数组来寻找第一个破坏升序的位置是为了确定无序子数组的起始边界。这种方法确实考虑到了所有可能破坏升序的情况,因为一旦发现一个元素比其前一个元素小,就表明从这一点开始数组已经不再满足全局升序的性质。这个位置标记了可能的无序子数组的开始,这是因为任何在这个位置之前的元素都不需要参与到后续的排序中,以保持整体数组的升序。
🦆
第二步从右到左扫描以寻找最后一个破坏升序的位置,这一步的逻辑是怎样的?即为什么要从数组的末尾开始扫描?
从右到左扫描数组以寻找最后一个破坏升序的位置是为了确定无序子数组的结束边界。这一步骤的目的是确保找到从右侧开始的、能够影响数组排序的最后一个元素。如果从左向右扫描,则可能错过右侧边界的准确位置,因为在某些情况下,数组的右侧部分可能比左侧更早破坏升序。从右向左扫描确保可以准确找到任何需要重新排序的元素,从而使整个数组达到全局升序。
🦆
在扩展区间 [l, r] 时,扩展的标准是基于什么?即为何要找到小于最小值 Min 和大于最大值 Max 的位置?
区间 [l, r] 的扩展是基于在这个区间内找到的最小值 Min 和最大值 Max。扩展的目的是确保数组中的任何元素如果小于区间的最小值或大于区间的最大值,都必须包括在内以进行重新排序。这是因为,即使 [l, r] 内的元素本身是无序的,如果区间外的元素小于 Min 或大于 Max,那么这些元素也会影响整体数组的排序。因此,为了确保整个数组升序,我们需要将这些元素包括在需要重新排序的子数组中。
🦆
如果数组中存在多个局部最小或最大值,这种方法能够准确地确定最短无序连续子数组的起始和结束位置吗?
是的,这种方法可以准确地确定最短无序连续子数组的起始和结束位置,即使数组中存在多个局部最小或最大值。该方法通过从左到右和从右到左的扫描确定了初始的 [l, r] 区间,然后通过扩展这个区间以包括所有小于 Min 或大于 Max 的元素,确保了捕获所有需要重新排序的元素。这种方式确保了无论局部极值如何分布,最终确定的 [l, r] 区间都将包括所有必须重新排序的元素,从而使整个数组达到全局升序。

相关问题