问题描述
由N个正整数组成的数组A.
存在阵列A的N × (N+1) / 2非空连续子阵列。
我们必须计算所有连续子阵列中存在的最大元素。
例如：
1 2 3
Subarray List :
[1]
[2]
[3]
[1,2]
[2,3]
[1,2,3]
Maximum Element :
[1]
[2]
[3]
[2]
[3]
[3]
我的方法：
使用Segment Tree查询区间中存在的最大元素
码：
public static void get_max_freq(int a , int b , ArrayList<Long> freq ,ArrayList<Integer> P , int n , int[] A){
if(a>b) return;
int index = query(1,0,n, a, b, A); // Segment Tree O(Logn)
long temp = (index-a+1)*(b-index+1);
freq.add(temp);
P.add(A[index));
get_max_freq(a,index-1, freq, P, n, A);
get_max_freq(index+1, b, freq, P,n, A);
}
我想知道如果元素在数组中不是唯一的，那么我的解决方案是正确的。
有没有比这更快更好的解决方案。
1楼
我认为你过于复杂了。
要构建一个分段树，你需要O(nlogn)空间，你将在O(n)时间内完成。
在此之后你将需要回答你的n(n+1)/2查询，每个查询都需要O（logn），所以基本上你会花费你O(n^2*logn) 。
Bruteforce方法（获取所有间隔并计算每个间隔的最大值）将在O(n)内存和O(n^3) 。
但您可以使用以下简单算法计算所有最大值。
让你的数组为[a0, a1, a2, ..., an] 。
从第0个元素开始，计算从该元素开始的范围内的所有最大值： max(a0-a0), max(a0-a1), ... max(a0-an) 。
您可以在O(n)执行此操作，因为max(ai-an) = max( max(ai-a(n-1)), an) （先前的最大和当前元素）。
因此，您计算a0的值，然后计算a1的值，依此类推O(n^2) 。
您可以存储它们，然后以您想要的格式输出它们。
你最后得到了O(n^2)空间和时间的超级简单算法。
PS注意到你不能及时做到比O(n^2)更好，因为你需要至少输出n*(n+1)/2元素，所以你只能希望减少空间复杂度。