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

Question

（cmp.https://leetcode.com/problems/shortest-unsorted-continuent-subarray/）。

我仍然停留在这个问题的主要方法上。它把我的头一分为二。

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

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

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

maxes:[1,2,5,5,7,10,10,12]

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

如果我从左边开始，它就变成了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    

null

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

从末尾查找最后一个索引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。