算法笔试模拟题精解之“过吊桥”
算法笔试模拟题精解之“过吊桥”
贡献者 | 郭达彬
简介：根据题意，要知道 B 同学还能在桥的一头逗留的时间，需要先求出什么时
候有连续的两块木板坏掉，或者第一块或者最后一块木板坏掉。
题目描述
题目等级：容易
知识点：贪心
查看题目：过吊桥
B 同学在机房敲了半个多月的代码之后终于打算出门玩一玩了。这天他准备去爬
山，当爬到了半山腰时，发现了一个吊桥。
这个吊桥总共由 n 块标号为 1-n 的木板组成，由于年久失修，这些木板有些已
经快要坏掉了，每块木板都有一个值 ai 表示第 i 块木板还有 ai 分钟就要坏掉了，即
在第 ai+1 分钟将无法站上这块木板。
B 同学过吊桥时一步只能走一块或两块木板，但是他想在吊桥的这边多玩一会。
请问他在吊桥这边最多可以玩多长时间？（可以认为 B 同学能在一分钟内通过吊
桥）特殊的，如果第一块或者最后一块木板坏掉的话吊桥就直接无法通过了。
输入一个整数 n, 表示总共有 n 块木板 (1<= n <= 10^5)。
再输入一个包含 n 个整数的数组，第 i 个数表示第 i 块木板还有 ai 分钟就要坏掉
了 (1 <= ai <= 10^9)。
输出一个整数表示 B 同学还能在桥的一头逗留的时间。
示例 1
输入：
4
[10,3,5,10]
输出：
5
注意
在第五分钟，还剩 124 三块木板可以通过，在第六分钟只剩下 14 两块木板就无
法通过了。
解题思路
根据题意，要知道 B 同学还能在桥的一头逗留的时间，需要先求出什么时候有连
续的两块木板坏掉，或者第一块或者最后一块木板坏掉。
首先将数组存入 HashMap 中，以数组的数为 key，索引的位置为 value（因为
数组中有可能会有相同的数字，而 value 值要存储所有数字的索引，所以索引只能以
List 的形式存在 value 中）。这样存储以后，只要知道数组中的数字，就能快速找到
其索引。
接下来对数组进行升序排序，再创建一个大小相同的数组 status 用来记录木板
的状态，然后遍历数组。
每遍历一个数，就通过 HashMap 查找其索引，在 status 数组中根据这个索引
将这个木板的状态置为 -1，代表木板坏掉了。然后判断是否符合不能通过桥的条件，
若符合条件，此时在数组遍历的数即为可以逗留的时间。若不符合条件，则继续遍历
数组，重复上述步骤，直到符合条件为止。
时间复杂度：O(n)
空间复杂度：O(2n)
看完之后是不是有了想法了呢，快来练练手吧 >> 查看题目：过吊桥
全站分卷索引 · 74 卷
- 1一、算法思想
- 2算法笔试模拟题精解之“打怪兽”
- 31.2 贪心
- 4算法笔试模拟题精解之“最强的团队”
- 5算法笔试模拟题精解之“Tom 爱吃巧克力”
- 6算法笔试模拟题精解之“吃奶酪”
- 7算法笔试模拟题精解之“一的个数”
- 8算法笔试模拟题精解之“Bob 的花束”
- 9算法笔试模拟题精解之“钱庄”
- 10算法笔试模拟题精解之“移动射击”
- 11算法笔试模拟题精解之“相似数组”
- 12算法笔试模拟题精解之“过吊桥”
- 13算法笔试模拟题精解之“完美排列”
- 14算法笔试模拟题精解之“采摘圣诞果”
- 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
- 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
- 17算法笔试模拟题精解之“学习小组”
- 18算法笔试模拟题精解之“恢复字符串”
- 191.3 DP/ 动态规划
- 20算法笔试模拟题精解之“寻找等比数列”
- 21算法笔试模拟题精解之“字符配对”
- 22算法笔试模拟题精解之“数组染色”
- 23算法笔试模拟题精解之“连绵的群山”
- 24算法笔试模拟题精解之“难住Tom 的问题”
- 25算法笔试模拟题精解之“变化的字符”
- 26算法笔试模拟题精解之“跳房子”
- 27算法笔试模拟题精解之“寒假活动”
- 28算法笔试模拟题精解之“最短路”
- 29算法笔试模拟题精解之“codancer 上楼”
- 30算法笔试模拟题精解之“木棒拼接”
- 31算法笔试模拟题精解之“Codancer 的数组封印”
- 32算法笔试模拟题精解之“Jerry 的异或运算”
- 33算法笔试模拟题精解之“小明的数学作业”
- 34算法笔试模拟题精解之“奇偶数列”
- 351.4 剪枝
- 361.5 尺取法
- 37算法笔试模拟题精解之“调整数组”
- 38算法笔试模拟题精解之“最优分组”
- 39算法笔试模拟题精解之“破译密码”
- 40二、数据结构
- 412.2 搜索
- 42算法笔试模拟题精解之“能量半径”
- 43算法笔试模拟题精解之“苹果收获程序”
- 44算法笔试模拟题精解之“恐怖的辐射”
- 45算法笔试模拟题精解之“树的拆分”
- 46算法笔试模拟题精解之“Password”
- 47算法笔试模拟题精解之“神奇数字在哪里”
- 48算法笔试模拟题精解之“神奇的棋子”
- 492.3 树
- 50算法笔试模拟题精解之“Codancer 的旅行”
- 51算法笔试模拟题精解之“Codancer 的求和”
- 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
- 532.4 线型
- 54算法笔试模拟题精解之“最活跃的数”
- 55算法笔试模拟题精解之“非递减序列”
- 56算法笔试模拟题精解之“Tom 跳方格”
- 57算法笔试模拟题精解之“复杂的字符串”
- 58算法笔试模拟题精解之“神秘消失”
- 59三、计算
- 60算法笔试模拟题精解之“简单题？
- 61算法笔试模拟题精解之“朋友一生一起走”
- 62算法笔试模拟题精解之“正三角塔”
- 63算法笔试模拟题精解之“组队难题”
- 64算法笔试模拟题精解之“2n 合体”
- 65算法笔试模拟题精解之“平行线”
- 66算法笔试模拟题精解之“叠叠高”
- 67算法笔试模拟题精解之“公平”
- 68算法笔试模拟题精解之“Tom 的手工课”
- 69算法笔试模拟题精解之“填数问题”
- 70算法笔试模拟题精解之“Jerry 的考验”
- 71算法笔试模拟题精解之“超车”
- 72算法笔试模拟题精解之“坏掉的时钟”
- 73算法笔试模拟题精解之“期末考试”
- 74算法笔试模拟题精解之“滑雪比赛”