最短未排序连续子数组：为什么我们从数组的末尾开始？

Question

我已经为这个问题苦苦思索了很久：

Given an integer array nums, 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.

(cmp.https://leetcode.com/problems/shortest-unsorted-continuous-subarray/).

我仍然停留在这个问题的主要方法上。它把我的头分成两半。

假设我们有这个给定的数组：

[1,2,5,3,7,10,9,12]

答案是“5”，属于“5”和“9”之间的子数组。

我对这个问题的处理方法基本上是这样的：

创建一个“maxes”数组，其中每个索引代表找到该索引之前的最大值。
创建一个“mins”数组，其中每个索引代表找到该索引之前的最小值。
'maxes'和输入数组之间的差异，以及'mins'和输入数组之间的差异，将给我们'start'和'end'索引。将两者相减得到子数组的长度。（这一步对我的问题不重要，我卡在这部分之前了。）

**

因此对于“maxes”数组，它看起来像：

输入：[1,2,5,3,7,10,9,12] ->

最大值：[1,2,5,5,7,10,10,12]

其中索引 0 为“1”，因为“1”是找到该索引的“最大值”。索引 1 是“2”，因为“2”是找到该索引的“最大值”。依此类推。

然后我们找到输入数组和 maxes 数组不匹配的最高索引。

我的问题是当我对 'mins' 数组尝试这种方法时：

输入：[1,2,5,3,7,10,9,12] ->

分钟：[1,1,1,1,1,1,1,1]

如果我从左边开始，它就变成了 1。

我应该从最后（右边）开始吗？如果我这样做了，为什么我必须在最后开始呢？

Answer 1

您的方法似乎总体上不错。你是正确的，你需要向后工作来构造 mins 数组。原因是当前最大值在 maxes 数组中向前“传播”的方式相同，当前最小值在 mins 数组中从末尾向后“传播”。

考虑输入数组 [2,3,5,1,12,7,10,9,11]，它的构建方式使得最短未排序连续子数组就是整个数组本身。

如果使用您的方法，您会发现最大值将 12 从中间“推”到末尾，最小值将 1 从中间“推”到最后开始。

Index    0  1  2  3  4  5  6  7  8

Input  [ 2, 3, 5, 1,12, 7,10, 9,11]
 
Maxes  [ 2, 3, 5, 5,12,12,12,12,12]
                                 ^
                             maxes_idx

Mins   [ 1, 1, 1, 1, 7, 7, 9, 9,11] 
         ^   
      mins_idx

对于您的数据，这会为您提供正确的索引：

Index    0  1  2  3  4  5  6  7

Input  [ 1, 2, 5, 3, 7,10, 9,12]
 
Maxes  [ 1, 2, 5, 5, 7,10,10,12]
                           ^
                         maxes_idx

Mins   [ 1, 2, 3, 3, 7, 9, 9,12] 
               ^   
            mins_idx

然后将长度计算为 length = maxes_idx - mins_idx + 1，在上述情况下为 length = 6 - 2 + 1 = 5。

除了使用两个序列 maxes 和 mins 执行此操作之外，您还可以将 input 与自身的排序版本进行比较，并从中找到两个索引：

排序 input 得到 sorted.
查找 lower_idx 作为 第一个 索引，其中 input 和 sorted 不匹配。
查找 upper_idx 作为 last 索引，其中 input 和 sorted 不匹配。
计算length = upper_idx - lower_idx + 1

Index    0  1  2  3  4  5  6  7

Input  [ 1, 2, 5, 3, 7,10, 9,12]
 
Sorted [ 1, 2, 3, 5, 7, 9,10,12]
               ^           ^ 
         lower_idx       upper_idx

后一种方法更容易掌握，但在复杂性方面更差（仅最快排序的时间复杂度为 O(n log n)）并且更多努力编写代码，以防您必须自己实施排序。

另一种方法（时间复杂度O(n)）根本不需要构造一个或多个版本的数组进行比较：

找到第一个索引i从头违反排序数组的条件（即 input[i] > input[i+1]）。

从末尾找到last索引j违反排序数组的条件（即input[j-1] > input[j])

Index 0 1 2 3 4 5 6 7 Input [ 1, 2, 5, 3, 7,10, 9,12] ^ ^ i=2 j=6

在这两个索引之间的子数组中，找到最小和最大元素

min_ij([5, 3, 7,10, 9]) = 3 max_ij([5, 3, 7,10, 9]) = 10

如果子数组的最小元素大于之前的所有元素，你就找到了i（你的例子就是这种情况）。否则，将 i 更新为完整数组中大于 min_ij.
的第一个元素的索引

如果子数组的最大元素小于之后的所有元素，那么你找到了j（你的例子就是这种情况）。否则，向后工作以将 j 更新为完整数组中小于 max_ij.
的最后一个元素的索引

将长度计算为 length = j - i + 1，在您的示例中为 length = 6 - 2 + 1 = 5.

最短未排序连续子数组：为什么我们从数组的末尾开始？

Shortest Unsorted Continuous Subarray: why do we start at the end of the array?

arrays

sorting

algorithm

sub-array