所有相邻子阵列中的最小元素

Question

我看到一个问题，要求它找到所有相邻子阵列的最小值。例如，对于数组A=[1,2,3]，答案将是一个包含[1,2,3,1,2,1]的数组B<怎么做-

B[0] = 1 for subarray A[0]  
B[1] = 2 for subarray A[1]  
B[2] = 3 for subarray A[2]  
B[3] = 1 for subarray A[0,1]  
B[4] = 2 for subarray A[1,2]  
B[5] = 1 for subarray A[0,1,2]

我所做的是，构建了一个段树，但是它不包含所有连续子数组的最小值。
我也不认为我可以使用“脱钩”，因为我不必在特定长度的子数组中找到最小值。
那么，我如何获得所有连续子阵列（B阵列）的最小值？

Answer 1

让我们看看，您可以简单地对输入数组进行排序，然后您将得到：

a_1

然后问题是：它们在B中存在多少次？

以a_i为例，只有当a_i位于以下连续子阵列中时，它才存在于B中：

a_i
a_i a_i（1）a_i a_i（1）。。。a_n

所以a_i在B中存在n-i 1次。

然后你可以简单地创建复杂度为O（n^2）的B（所有相邻子数组的数量是C（n，2）=O（n^2））。

更新：此解决方案仅适用于已排序的A。

Answer 2

一个简单的O（n^2）解决方案（而不是带有段树的O（n^2 log n））是使用动态编程ish算法：

从一个等于A的数组T开始，但在每一步中，在T中的每个元素前面，你都要计算一个最小值。

T1 = min(1..1), min(2..2), min(3..3)

T2 = min(1..2), min(2..3), <bogus>

T3 = min(1..3), <bogus>  , <bogus>

下面是Python中的一个例子：

def solve(A):
    T = list(A)
    B = list(A)

    for k in range(1, len(A)):
        for i in range(len(A)-k):
            T[i] = min(T[i], A[i+k])
            B.append(T[i])

    return B

print solve([1,2,3])

Answer 3

下面是使用段树的实现：

#include <stdio.h>
#include <math.h>
#include <limits.h>
#include <iostream>

using namespace std;

int Mid(int s, int e) {  return s + (e -s)/2;  }
int RMQUtil(int *st, int ss, int se, int qs, int qe, int index) {
    if (qs <= ss && qe >= se)
        return st[index];
    if (se < qs || ss > qe)
        return INT_MAX;

    int mid = Mid(ss, se);
    return min(RMQUtil(st, ss, mid, qs, qe, 2*index+1),
                  RMQUtil(st, mid+1, se, qs, qe, 2*index+2));
}
int RMQ(int *st, int n, int qs, int qe) {
    if (qs < 0 || qe > n-1 || qs > qe)
    {
        printf("Invalid Input");
        return -1;
    }

    return RMQUtil(st, 0, n-1, qs, qe, 0);
}
int constructSTUtil(int arr[], int ss, int se, int *st, int si) {
    if (ss == se) {
        st[si] = arr[ss];
        return arr[ss];
    }
    int mid = Mid(ss, se);
    st[si] =  min(constructSTUtil(arr, ss, mid, st, si*2+1),
                     constructSTUtil(arr, mid+1, se, st, si*2+2));
    return st[si];
}
int *constructST(int arr[], int n) {
    // Allocate memory for segment tree
    int x = (int)(ceil(log2(n)));
    int max_size = 2*(int)pow(2, x) - 1;
    int *st = new int[max_size];

    // Fill the allocated memory st
    constructSTUtil(arr, 0, n-1, st, 0);
    return st;
}
int main()
{
    int arr[] = {1, 2, 3};
    int n = sizeof(arr)/sizeof(arr[0]);

    int *st = constructST(arr, n);

    int qs = 0; //start
    int qe = 2; //end
    int s = 0;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n - s; ++j) {
            cout << RMQ(st, n, j, j + s) << " ";
        }
        s += 1;
    }
    cout << endl;

    return 0;
}

当然你可以用德克。找到一种方法，使最小的元素总是出现在Q的前面，并且Q的大小永远不会超过L。复杂性：O（n）