arrays - 所有连续子数组中的最小元素

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

下面是使用线段树的实现:

#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)