计算大数组中从[currPos]到[currPos - k]的最大值

Question

我正在为ACM比赛做准备,我坚持这个问题.

您的建筑物具有给定位置Xi和高度Hi,盾牌由钢制成,并且它们需要由至少两个相同高度的建筑物支撑.盾牌的右端必须位于某栋建筑的顶部.所有位于盾牌下方的建筑物(包括位于末端的建筑物)都受到该盾牌的保护,其高度不能超过盾牌所在的高度.一栋建筑最多可以保护一个盾牌.

您将获得无数个盾牌,每个盾牌具有相同的长度L.找到可由盾牌保护的最大建筑物数量,并找到可用于保护最大建筑物数量的最小盾牌数量.

输入

第一行输入包含一个正整数T(1 <= T <= 20),即测试用例的数量.

每个测试用例以一条恰好包含两个整数的行开始:建筑物数量N(2 <= N <= 100,000)和盾牌L的长度(1 <= L <= 1,000,000,000).在接下来的N行中,有两个整数,Xi(第i个建筑物的位置,0 <= Xi <= 1,000,000,000)和Hi(第i个建筑物的高度,1 <= Hi <= 1,000,000,000 ).建筑物按x坐标排序.不会有两个具有相同x坐标的建筑物.

产量

对于每个测试用例,在两条线上输出可覆盖的最大建筑物数量以及可用于此目的的最小屏蔽数量.

例

Input
17 3
1 2
2 1
3 2
4 3
5 1
6 2
7 4
8 2
9 3
10 4
11 2
15 2
16 1
17 3
18 3
19 1
20 2

Output
11 3

Explanation:
first shield: 1,2,3 
second shield: 7,8,9,10
third shield:  15,16,17,18

显然蛮力解决方案很容易编码代码,但会在时间限制(1s)上失败,我正在阅读有关分段树的内容,但由于我没有使用分段树,我感兴趣的是解决此问题的方法或我错过了一些更简单的解决方案吗？

PS虽然它说盾长度是L,但它实际上是L + 1,最后一座建筑必须是最高的并且在位置[Xi-1,Xi-L]上有一个建筑物,高度相同,能够放置盾牌和建筑物位置被分类.

Answer 1

pos - k寻找从到 的最大值pos也称为“滑动窗口最大值问题”，它有一个简单的O(N)解决方案，无需线段树或任何其他高级数据结构。
该算法如下：
1）让我们维护一个deque对<value, position>。
2）移动窗口边界是通过以下方式完成的（我在这里使用伪代码）：

//Moving the right border.
right <- right + 1
cur <- pair<value[right], x[right]>
while not deque.empty and deque.back.value < cur.value
    deque.pop_back()
deque.push_back(cur)

//Moving the left border.
left <- left + 1
while deque.front.position is out of [x[left], x[right]] bounds
    deque.pop_front()

3）最大值很简单deque.front.value。

该算法的复杂性在于O(N)，每个元素仅被推送到双端队列一次，并且仅从双端队列中删除一次（并且while上面伪代码中的循环的每次迭代都会从双端队列中删除一个元素）。

现在关于盾牌的原始问题的解决方案：
1）让我们假设dp[pos]=pair<覆盖的建筑物的最大数量，使用的盾牌的最小数量>使得所有盾牌的右边界是<= pos。
2）让我们维护两个指针low和high。是high指向当前建筑物的指针，该low指针是指向最左边建筑物的指针，使得x[high] - x[low] >= L。
3)high循环中指针总是加1 for，并且low指针会被适当调整（以满足2）属性）。
4)Thendp可以通过以下方式计算：对于 的固定值high，dp[high]是dp[high - 1]或dp[low - 1] + high - low + 1（仅当可以从low到放置屏蔽时才使用第二个high）。
5）如何检查是否可以放置屏蔽？使用滑动窗口最大值算法，可以维护范围内的最大值[low; high - 1]并检查它是否等于H[high]。
6）答案是dp[N - 1]（从0开始的索引）。

该解决方案的复杂性是O(N)因为low和high总是递增的，并且它们不能递增超过N多次，并且滑动窗口最大算法复杂性如上所示。