找到创建数组的最严格上限（在几个选项中）
Find the tightest upper bound for a creation of an array (among few options)
让A，一个数字数组。我们需要创建一个数组 B 使得 B[i] = min(A[i],...,A[i+sqrt(n)].
为什么创建B的最紧上限是O(nlogn)？
我实际上得到了一个选项列表：
O(sqrt(n)*logn)O(n/logn)O(n*logn)O(nlog(n)^2)O(n*sqrt(n))O(n^2)
答案是 O(nlogn)，因为它是最低但不是次线性的选项。
可以在 O(nlogn) 中通过维护大小为 sqrt(n) 的已排序 DS（例如自平衡 BST）来完成，并迭代地删除和添加元素（而 运行数组上的滑动 window）。
每次迭代在 O(log(sqrt(n)) = O(1/2*log(n)) = O(logn) 中完成，并且有 O(n) 次迭代，因此总共 O(nlogn)。
这取消了所有 "higher" 个备选方案的资格，并且所有 "lower" 个备选方案都是次线性的，并且您不能在次线性时间内创建数组。
让A，一个数字数组。我们需要创建一个数组 B 使得 B[i] = min(A[i],...,A[i+sqrt(n)].
为什么创建B的最紧上限是O(nlogn)？
我实际上得到了一个选项列表：
O(sqrt(n)*logn)O(n/logn)O(n*logn)O(nlog(n)^2)O(n*sqrt(n))O(n^2)
答案是 O(nlogn)，因为它是最低但不是次线性的选项。
可以在 O(nlogn) 中通过维护大小为 sqrt(n) 的已排序 DS（例如自平衡 BST）来完成，并迭代地删除和添加元素（而 运行数组上的滑动 window）。
每次迭代在 O(log(sqrt(n)) = O(1/2*log(n)) = O(logn) 中完成，并且有 O(n) 次迭代，因此总共 O(nlogn)。
这取消了所有 "higher" 个备选方案的资格，并且所有 "lower" 个备选方案都是次线性的，并且您不能在次线性时间内创建数组。