遇到一个过吊桥问题，求解答。
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 同学还能在桥的一头逗留的时间。
写回答
-
根据题意可知，要知道B同学还能在桥的一头逗留的时间，需要先求出什么时候有连 续的两块木板坏掉，或者第一块或者最后一块木板坏掉。首先将数组存入HashMap中，以数组的数为key，索引的位置为 value（因为数组中有可能会有相同的数字，而 value值要存储所有数字的索引，所以索引只能以List 的形式存在value中）。这样存储以后，只要知道数组中的数字，就能快速找到其索引。接下来对数组进行升序排序，再创建一个大小相同的数组status用来记录木板的状态，然后遍历数组。每遍历一个数，就通过HashMap查找其索引，在 status数组中根据这个索引将这个木板的状态置为 -1，代表木板坏掉了。然后判断是否符合不能通过桥的条件，若符合条件，此时在数组遍历的数即为可以逗留的时间。若不符合条件，则继续遍历数组，重复上述步骤，直到符合条件为止。 输入：4 [10,3,5,10] 输出：5
2021-12-23 18:27:58赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
