Минимальные элементы во всех смежных подмассивах

Question

Я увидел вопрос, где его попросили найти минимум всех смежных подмассивов. Для примера. Для массива A = [1,2,3] ответом будет массив B, содержащий [1,2,3,1,2,1].
Как -

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] 

То, что я сделал, это, построил дерево сегмент, но он не содержит минимум всех смежных подмассивов.
Я не думаю, что могу использовать «Dequeues», потому что мне не нужно найти min в подмассиве определенной длины.
Итак, как я могу получить мин. всех смежных подмассивов (массив 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; 
} 

Конечно, вы можете использовать Deque. Найдите способ, чтобы наименьший элемент всегда отображался в передней части Q, а размер Q никогда не превышал L. Сложность: O (n)

Answer 2

Простое решение O (n^2) (вместо O (n^2 log n) с деревом сегментов) заключается в использовании динамического алгоритма программирования-иша:

Вы начинаете с массива T, равного A, но на каждом шаге вы вычисляете еще один минимум впереди каждого элемента в Т.

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

Давайте посмотрим, что вы можете просто отсортировать массив ввода, а затем у вас есть:

a_1 <= a_2 <= ... <= a_n,

тогда вопрос: сколько раз каждый из них существует в B?

Так возьмите a_i, она существует в B только тогда, когда a_i находится в следующих смежных подмассивов:

a_i
a_i a_(i+1)
...
a_i a_(i+1) ... a_n

a_i Так существует n-i+1 раз в B ,

Итак, вы можете просто создать B с сложностью O (n^2) (число всех смежных подмассивов - C (n, 2) = O (n^2)).

UPDATE: Это решение OK только для отсортированного А.