寻找非固定长度x的每个子阵列的最小的最大值，其中1 <= X <= N

Question

访问：

您在阵列中给出Ñ号码。一个数字的一​​个组是阵列的非空连续区段。一个组的大小是该组中的号的数目。

让甲是一组中的最小数目。的任务是找到每个X（1 < = X < = N），的甲大小X的所有组中的最大值。例如，如果N = 3并且数组为[1,2,3]，则答案将是3（x = 1），2（x = 2），1（x = 3） 。

数字可以在阵列（例如，在被重复，用于Ñ = 7，阵列可以是[1,2,3,4,5,4,6]。

对于解释，所述下面的C代码是一个天真的解决方案：

#include <stdio.h> 

int main() { 
    int a[] = {6,1,3,2,5,4,7}; 
    size_t N = sizeof a/sizeof *a; 

    for (size_t i=0; i<N; ++i) printf("%d ", a[i]); puts("\n"); 

    size_t group_size, start, i; 
    int max, min; 
    for (group_size = 1; group_size <= N; ++group_size) { 
     max = 0; 
     for (start = 0; start <= N - group_size; ++start) { 
      min = a[start]; 
      for (i = start + 1; i < start + group_size; ++i) { 
       if (a[i] < min) 
        min = a[i]; 
      } 
      if (min > max) 
       max = min; 
     } 
     printf("%d ", max); 
    } 

    return 0; 
} 

输出：

6 1 3 2 5 4 7 

7 4 4 2 2 1 1 

Answer 1

非常简短草图：对于每个阵列元素，计算用于该该元素是最小的最大组的大小。 （通过将两个相等元素中的第一个相同元素视为较小来断开连接。）使用退化的桶排序按线性时间对元素进行排序。按大小扫描元素，输出到目前为止所看到的最大元素（即组大小满足当前阈值的最大元素）。

棘手的一步是计算组大小。我们保留一个堆栈并开始扫描数组。对于每个元素，我们弹出大于它的堆栈元素，从而结束它们的组。以下是6 1 3 2 5 4 7的跟踪。

stack: (-inf @ -1) {sentinel} 

6 1 3 2 5 4 7 -inf {sentinel} 
^ 
stack: (-inf @ -1), (6 @ 0) 

6 1 3 2 5 4 7 -inf 
^
pop (6 @ 0): group size of 6 is (1 - (-1)) - 1 = 1 
stack: (-inf @ -1), (1 @ 1) 

6 1 3 2 5 4 7 -inf 
    ^
stack: (-inf @ -1), (1 @ 1), (3 @ 2) 

6 1 3 2 5 4 7 -inf 
    ^
pop (3 @ 2): group size of 3 is (3 - 1) - 1 = 1 
stack: (-inf @ -1), (1 @ 1), (2 @ 3) 

6 1 3 2 5 4 7 -inf 
     ^
stack: (-inf @ -1), (1 @ 1), (2 @ 3), (5 @ 4) 

6 1 3 2 5 4 7 -inf 
     ^
pop (5 @ 4): group size of 5 is (5 - 3) - 1 = 1 
stack: (-inf @ -1), (1 @ 1), (2 @ 3), (4 @ 5) 

6 1 3 2 5 4 7 -inf 
      ^
stack: (-inf @ -1), (1 @ 1), (2 @ 3), (4 @ 5), (7 @ 6) 

6 1 3 2 5 4 7 -inf 
      ^
pop (7 @ 6): group size of 7 is (7 - 5) - 1 = 1 
pop (4 @ 5): group size of 4 is (7 - 3) - 1 = 3 
pop (2 @ 3): group size of 2 is (7 - 1) - 1 = 5 
pop (1 @ 1): group size of 1 is (7 - (-1)) - 1 = 7 
stack: (-inf @ -1), (inf @ 7) 

Answer 2

这个问题又是用华丽的词藻所有你需要计算的是（X - 1）个重最大数量。 verse排序数组。

要看到这一点，假设你有一种形式的数组：

A = [12, 14, 26, 50, 43]; 

如果你解决它，它将成为

A' = [12, 14, 26, 43, 50]; 

现在，需要最大限度的最小值任何子阵，将长度x的子阵列从端部开始时。因为对于所有其它可能的子阵列，比从端第x个元素更小的元素将要在那里，从而降低了最小值。

所以为了得到答案，你只要反向排序阵列，并且在指数（X - 1）的元素是你的答案。

A'' = [50, 43, 26, 14, 12] 

可以很容易地计算出非固定长度x的每个子阵列的最小值的最大值。

编辑：

例如见对于x从1至3

Length 1: 50 
Length 2: 43 
Length 3: 26 

等。

EDIT2：

如果所有的元素是唯一这样才有效。

Answer 3

这是O（n ）解决方案。

将输出数组设置为空并将输入数组a设置为初始值。

虽然一个是非空的：

• 计算的一个附加最大值开始输出数组
• 上一个执行收缩操作，其中每个元件的〔 i]设置为a [i]和a [i + 1]中的最小值，并且删除最后一个元素

例如：

output = [] 
a = [1,2,3,4,5,4,6] 
output = [6] // add max of a to start of output array 
a = [1,2,3,4,4,4] // shrink array 
output = [4,6] // add max of a to start of output array 
a = [1,2,3,4,4] // shrink array 
output = [4,4,6] // add max of a to start of output array 
a = [1,2,3,4] // shrink array 
output = [4,4,4,6] // add max of a to start of output array 
a = [1,2,3] // shrink array 
output = [3,4,4,4,6] // add max of a to start of output array 
a = [1,2] // shrink array 
output = [2,3,4,4,4,6] // add max of a to start of output array 
a = [1] // shrink array 
output = [1,2,3,4,4,4,6] // add max of a to start of output array 
a = [] 

在循环的第一次迭代开始时，一个将包含最小长度1的所有组（只是初始值）的。在第二次迭代开始时，它将包含所有长度为2的组的最小值，依此类推。

在每次迭代中，元素的最小一个[I]至[j]的（分钟（A [1] ...一个[j]的））将等于

分钟（分钟（一[i] ... a [j-1]），min（a [i + 1] ... a [j]））

因此，您可以计算基于相邻组的长度为n的组的最小值长度为n-1。

的C代码：一个线性时间溶液

#include <stdio.h> 

int main() { 
    int a[] = {6,1,3,2,5,4,7}; 
    size_t i, N = sizeof a/sizeof *a; 

    for (i=0; i<N; ++i) printf("%d ", a[i]); puts("\n"); 

    while(N > 0) 
    { 
     int max = a[0]; 
     for(i = 0; i < N - 1; i++) 
     { 
      if(a[i+1] > max) 
       max = a[i+1]; 
      a[i] = a[i+1] < a[i] ? a[i+1] : a[i]; 
     } 
     printf("%d ", max); 
     N--; 
    } 

    return 0; 
} 

Demo