找到非固定长度 x 的每个子数组的最小值的最大值，其中 1<= x <= N

Question

面试问题：

给你 N 个数组中的数字。组的数字是数组的非空连续段。一组的大小是该组中数字的数量。

设A为一组中的最小数。任务是为每个 x (1 <= x <= N) 找到 A[= 的最大值35=] 在大小为 x.

的所有组中
例如，如果 N = 3 并且数组是 [1,2,3]，那么答案将是 3 (x = 1), 2 (x = 2), 1 (x = 3).

数组中的数字可以重复（比如N = 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

这道题是花言巧语。您只需要计算反向排序数组中的第 (x - 1) 个最大数。

要查看此内容，假设您有一个以下形式的数组：

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

排序的话会变成

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

现在，任何需要最大化最小值的子数组，从末尾开始就是长度为x的子数组。因为对于所有其他可能的子数组，必须存在小于从 end 开始的第 x 个元素的元素，从而减少最小值。

所以要得到你的答案，你只需对你的数组进行反向排序，索引 (x - 1) 处的元素就是你的答案。

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

每个非固定长度的子数组x的最大值和最小值很容易计算出来

编辑：

例如 x 从 1 到 3

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

等等。

EDIT2:

这只有在所有元素都是唯一的情况下才有效。

Answer 2

这是一个 O(n²) 的解决方案。

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

虽然 a 不为空：

计算 a 的最大值并添加到输出数组的开头
对a进行收缩操作，其中每个元素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 = []

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

在每次迭代中，元素 a[i] 到 a[j] 中的最小值 (min(a[i]...a[j])) 将等于

min(min(a[i]...a[j-1]),min(a[i+1]...a[j]))

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

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

Answer 3

线性时间解决方案的非常简短的草图：对于每个数组元素，计算该元素为最小值的最大组的大小。（通过将两个相等元素中的第一个视为更小来打破平局。）使用退化桶排序在线性时间内按元素的关联大小对元素进行排序。按大小从大到小扫描元素，输出目前看到的最大元素（即分组大小满足当前阈值的最大元素）。

棘手的步骤是计算组大小。我们保留一个堆栈并从头到尾扫描数组。对于每个元素，我们弹出比它大的堆栈元素，从而结束它们的组。这是 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)

找到非固定长度 x 的每个子数组的最小值的最大值，其中 1<= x <= N

Find the maximum value of minimum of each subarray of non fixed length x where 1<= x <= N

algorithm

dynamic-programming