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

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数组）的最小值？

- Mayank Baiswar

---

B 的顺序重要吗？ - jan_kowalski_314

@jan_kowalski_314 不。 - Mayank Baiswar

@MayankBaiswar 你真的需要数组B吗？还是你只需要知道每个元素成为最小值的次数？ - Juan Lopes

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;
}

当然，您可以使用双端队列。找到一种方法，使得最小的元素始终出现在队列的前面，并且队列的大小永远不会超过L。时间复杂度：O(n)

- Rasul Kerimov

---

这是最优复杂度吗？ - Mayank Baiswar

这个解决方案不是O(n)。它以O(log n)的代价生成O(n^2)个元素。总体复杂度为O(n^2 log n)。 - Juan Lopes

@JuanLopes 的 O(n) 解决方案是使用双端队列（我还没有弄清楚）。 - Mayank Baiswar

@mayank，我现在无法为您编写解决方案。但是您可以在此处查看：https://dev59.com/FmfWa4cB1Zd3GeqPmPz9#12239580。在那个问题中，他试图找到局部最大值。您需要修改代码。 - Rasul Kerimov

@juan，你对复杂度的看法是正确的。但O(n)是针对双端队列实现的。 - Rasul Kerimov

@James 在一个大小为n的数组中，有O(n^2)个子数组。不可能有O(n)算法。下限是O(n^2)。 - Juan Lopes

Answer 2

一个简单的O(n^2)解法（而不是用线段树的O(n^2 log n)解法）是使用类似于动态规划的算法：

你从一个等于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])

- Juan Lopes

---

应该是 T1 = ... , min(3..3) 吗？ - beaker

Answer 3

我们来看一下，你可以简单地对输入数组进行排序，然后得到：

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

那么问题是：每个元素在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。

- jan_kowalski_314

---

元素在B中出现的次数取决于A的顺序。如果 A=[1, 2, 3]，则 B=[1, 2, 3, 1, 2, 1]。如果 A=[2, 1, 3]，则 B=[2, 1, 3, 1, 1, 1]。此外，我认为B的顺序也很重要，但我不确定。 - Juan Lopes

我希望那不是很重要的事情。如何创建下一个子数组并没有被视为重要的事情，但这很容易改变，我们只需要采取1,2,...n,1,2...,n-1,1,2,...,n-2, etc. 1。这非常容易 :) - jan_kowalski_314

无论如何，在我之前的评论中给出的反例中，你的算法仍然返回错误的结果。请注意，在正确答案中，“1”出现了4次，而在你的算法中只会出现3次。 - Juan Lopes

即使B的顺序不重要，你的答案仍然给出了错误的元素。请看我的第一条评论：A=[1,2,3]和A=[2,1,3]应该有不同的结果。你的算法将它们视为相等。 - Juan Lopes

@JuanLopes 您的解决方案对于每种情况都是最好的，而且更加优秀。 - jan_kowalski_314