使A[0]<A[k]，A[1]<A[k+1]，.，A[k-1]<A[2*k-1]，在对每一个k大小的窗口进行排序之后的最大k
使A[0]<A[k]，A[1]<A[k+1]，.，A[k-1]<A[2*k-1]，在对每一个k大小的窗口进行排序之后的最大k
提问于 2021-07-28 02:52:05
我需要这个问题的有效算法(时间复杂度小于O(n^2))，请帮助我：
ai.j称为ai.j给定数组A1.n，(n<= 10^5，ai<= 1000)。找出a1.k< Ak+1..2k的最大值，例如，n=10: 2 2 1 4 3 2 5 4 2 3答案是4
很容易看到k，<=，n/2，所以我们可以使用蛮力(k从n/2到1)，而不是二进制搜索。
我不知道该如何处理ai <= 1000。也许用地图？
回答 1
Stack Overflow用户
回答已采纳
发布于 2021-10-09 10:12:25
使用具有范围更新的芬威克树。树中的每个索引表示窗口A中有多少数字比它小。要使窗口有效，B中的每个元素(右边的窗口)必须在A中有一个合作伙伴(左边的窗口)。当我们将一个数字x转换为A时，我们将1添加到树中的范围，[x+1, 1000]。对于从B转移到A的元素，在其树索引中添加1。对于B中的每个新元素，将-1添加到树中的索引中。如果索引降到零以下，则窗口无效。
例如，我们有：
2 2 1 4 3 2 5 4 2 3
2 2
|
Tree:
add 1 to [3, 1000]
add -1 to 2
idx 1 2 3 4 5
val 0 -1 1 1 1 (invalid)
2 2 1 4 3 2 5 4 2 3
2 2 1 4
|
Tree:
add 1 to [3, 1000]
add 1 to 2 (remove 2 from B)
add -1 to 1
add -1 to 4
idx 1 2 3 4 5
val -1 0 2 1 2 (invalid)
2 2 1 4 3 2 5 4 2 3
2 2 1 4 3 2
|
Tree:
add 1 to [2, 1000]
add 1 to 1 (remove 1 from B)
add -1 to 3
add -1 to 2
idx 1 2 3 4 5
val 0 0 2 2 3 (valid)
2 2 1 4 3 2 5 4 2 3
2 2 1 4 3 2 5 4
|
Tree:
add 1 to [5, 1000]
add 1 to 4 (remove 4 from B)
add -1 to 5
add -1 to 4
idx 1 2 3 4 5
val 0 0 2 2 3 (valid)
2 2 1 4 3 2 5 4 2 3
2 2 1 4 3 2 5 4 2 3
|
Tree:
add 1 to [4, 1000]
add 1 to 3 (remove 3 from B)
add -1 to 2
add -1 to 3
idx 1 2 3 4 5
val 0 -1 2 3 4 (invalid)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/68553799
复制相关文章
相似问题
腾讯云开发者
