时间戳

首页 > 解决方案 > 求最大长度子数组条件 2 * min > max

arrays - 求最大长度子数组条件 2 * min > max

问题描述

这是我最近在 Adob​​e 被问到的一个面试问题：

在一个数组中，找到条件为 的最大长度子数组，2 * min > max其中min是子数组的最小元素， 是子max数组的最大元素。

有没有人有比 O(n^2) 更好的方法？
当然，我们不能排序，因为需要子数组。

以下是我的 O(n^2) 方法：

max=Integer.MIN_VALUE;
for (int i=0; i<A.length-1;i++)
  for(j=i+1;j<A.length;j++)
  {
    int min =findMin(A,i,j);
    int max =findMAx(A,i,j);
    if(2*min<=max) {
      if(j-i+1>max) 
        max = j-i+1
    }
  }

有人知道 O(n) 解决方案吗？

标签： arraysalgorithm

解决方案

令A [ i ...<em>j] 是由A [ i ]、A [ i +1]、... A [ j ] 组成的子数组。

观察：

  • 如果A [ i …<em>j] 不满足条件，那么A [ i …( j +1)] 也不满足，因为 2·min( A [ i …( j +1)]) ≤ 2· min( A [ i ...<em>j]) ≤ max( A [ i ...<em>j]) ≤ max( A [ i ...( j +1)])。因此，您可以在发现j不满足条件的情况下立即中止内部循环。
  • 如果我们已经找到符合条件的长度为L的子数组，则无需考虑任何长度≤ L的子数组。j = i + maxLength所以你可以用而不是开始你的内部循环j = i + 1。（当然，您需要初始化maxLength为0而不是Integer.MIN_VALUE。）

结合以上，我们有：

int maxLength = 0;
for (int i = 0; i < A.length; ++i) {
    for (int j = i + maxLength; j < A.length; ++j) {
        if (findMin(A,i,j) * 2 > findMax(A,i,j)) {
            // success -- now let's look for a longer subarray:
            maxLength = j - i + 1;
        } else {
            // failure -- keep looking for a subarray this length:
            break;
        }
    }
}

乍一看可能并不明显，但内部循环现在总共只经历了O ( n ) 次迭代，因为j每个值最多只能取一次。（例如，如果i是 3 并且maxLength是 5，则从j8 开始。如果我们A [3…8] 满足条件，我们递增maxLength直到找到不满足条件的子数组。一旦发生这种情况，我们从A [ i …( i + maxLength )] 到A [( i +1)…(( i +1)+ maxLength )]，这意味着新循环以更大的开始j比上一个循环停止。）

我们可以通过重构将A [ i ...<em>j] 建模为滑动和潜在扩展窗​​口来使这一点更加明确：递增i从窗口的左边缘删除一个元素，递增j将一个元素添加到窗口的右边缘，并且永远不需要在不增加的i情况下增加j：

int maxLength = 0;
int i = 0, j = 0;
while (j < A.length) {
    if (findMin(A,i,j) * 2 > findMax(A,i,j)) {
        // success -- now let's look for a longer subarray:
        maxLength = j - i + 1;
        ++j;
    } else {
        // failure -- keep looking for a subarray this length:
        ++i;
        ++j;
    }
}

或者，如果您愿意：

int maxLength = 0;
int i = 0;
for (int j = 0; j < A.length; ++j) {
    if (findMin(A,i,j) * 2 > findMax(A,i,j)) {
        // success -- now let's look for a longer subarray:
        maxLength = j - i + 1;
    } else {
        // failure -- keep looking for a subarray this length:
        ++i;
    }
}

由于在您的解决方案中，内部循环总共迭代O ( n 2 ) 次，并且您已经声明您的解决方案在O ( n 2 ) 时间内运行，我们可以争辩说，因为上面只有内部循环迭代O ( n ) 次，以上必须在O ( n ) 时间内运行。

问题是，这个前提真的很可疑。您没有说明如何实现findMinand findMax，但直接的实现将花费O ( j −<em>i) 时间，这样您的解决方案实际上在O ( n 3 ) 而不是O ( n 2 ) 中运行。因此，如果我们将内循环迭代次数从O ( n 2 ) 减少到O ( n )，那只会将总时间复杂度从O ( n 3 ) 降低到O ( n 2 )。

但是，碰巧的是，可以使用https://www.geeksforgeeks.org/sliding上的“方法 3”在分摊的O (1) 时间和O ( n ) 额外空间中计算这些子数组的最小值和最大值-window-maximum-maximum-of-all-subarrays-of-size-k/。（向גלעד ברקן指出这一点。）它的工作方式是，您维护两个双端队列，minseq用于计算最小值和maxseq计算最大值。（我只会解释minseq;maxseq是类似的。）在任何给定时间，第一个元素（头）是A [ i ...<em>j];minseq中 min 元素的索引；第二个元素minseq是第一个元素之后的最小元素的索引；等等。（因此，例如，如果子数组从索引 #2 开始是 [80,10,30,60,50]，那么minseq将是 [3,4,6]，它们是子序列 [10,30, 50]。）每当你增加i时，你检查旧值i是否是头部minseq（意味着它是当前最小值）；如果是这样，你移除头部。每当您递增j时，您都会重复检查尾部是否minseq是大于或等于元素的索引j；如果是这样，您删除尾巴并重复。一旦你删除了所有这样的尾部元素，你就可以添加j到尾部。由于每个索引最多被添加到双端队列和从双端队列中删除一次，所以这个记账的总成本为O ( n )。

根据需要，这为您提供了总体O ( n ) 时间。

推荐阅读