计算大数组中从[currPos]到[currPos - k]的最大值
我正在为ACM比赛做准备，我被这个问题困住了。
你有一个给定位置的建筑物，，Xi，，，，，盾牌是用钢做的，它们需要至少有两个高度相同的建筑物支撑。防护罩的右端必须位于某座建筑物的顶部。所有位于盾牌下的建筑物(包括那些躺在最后的建筑物)都受到该盾牌的保护，其高度不能超过设置盾牌的高度。一个建筑物最多可以用一个盾牌来保护。 给你无限数量的盾牌，每个盾牌长度相同。找出可以被盾牌保护的建筑物的最大数量，并找到可以用来保护最大建筑数量的最小的盾牌数目。 输入 第一行输入包含一个正整数T (1 <= T <= 20)，测试用例数。 每个测试用例都从一个包含两个整数的行开始:建筑物数N (2 <= N <= 100,000)和屏蔽L的长度(1 <= L <= 1,000,000,000)。在接下来的N行中，每一行都有两个整数，Xi (第一层建筑的位置，0 <= Xi <= 1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,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)上失败，我读过关于段树的文章，但由于我没有使用段树，所以我感兴趣的是解决这个问题的方法，还是我忽略了一些更简单的解决方案？
虽然它说盾牌长度是L，但实际上是L+1，最后一栋建筑必须是最高的，并且有一座建筑在位置为Xi-1，西安-L具有相同的高度才能放置一个盾牌，建筑的位置将被分类。
回答 1
Stack Overflow用户
发布于 2014-06-21 13:24:04
求出从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)，因为每个元素只被推到deque上一次，并且只从deque中删除一次(伪代码中的while循环的每一次迭代都会从deque中删除一个元素)。
现在，关于屏蔽的原始问题的解决方案：
1)让我们假设dp[pos] =所覆盖的建筑物的pair的最小数目，这样所有盾牌的右边框都是<= pos。
2)让我们维护两个指针low和high。high是当前建筑物的指针，low指针是指向最左边的建筑物的指针，例如x[high] - x[low] >= L。
3)high指针在for循环中总是以1递增，low指针被适当地调整(以满足2)属性。
4)然后可以按以下方式计算dp：对于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次数，而且滑动窗口的最大算法复杂度在上面给出了显示。
https://stackoverflow.com/questions/24340967
复制相似问题
腾讯云开发者
