在最近的一次采访中,我遇到了以下问题.
在一个特定的城市,我们有一排不同高度的建筑物.高度为h的建筑物倒塌导致其右侧的下一个h-1建筑物也会倒塌.建筑物的高度可以在1到5000之间.鉴于所有建筑物的高度(从左到右排列,即最左边的建筑物指数= 1,最右边的建筑物指数= N),我们需要找出建筑物会造成最大的破坏.
例如:
输入:建筑物数量:6
建筑物高度:2 1 3 3 1 6
答案应该在索引3处建立
我尝试的解决方案是使用蛮力技术,复杂度为O(N ^ 2).我所做的是列表中的每个建筑物,我发现它会破坏的建筑物数量.
可以为这个问题构建一个更好的解决方案吗？
Kar*_*ath 10
只需从左侧开始,折叠第一座建筑物,然后计算它造成的总损失(*).
从下一个建筑物(没有倒塌)一次又一次地这样做.
从这些,挑选最大值.
复杂性:O(n).
这种贪婪的算法是有效的,因为整个过程是一个连锁反应,如果建筑A强迫B崩溃,那么你就无法从B开始获得更好的分数.
(*)您可以通过维护一个计数器来执行此操作,该计数器存储右侧应该折叠多少个建筑物. counter = max(counter - 1, height of next building).
| 归档时间： |
|
| 查看次数： |
217 次 |
| 最近记录： |