算法笔试模拟题精解之“过吊桥”

在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：

https://developer.aliyun.com/coding

本文为大家介绍其中的 第85题：过吊桥 的题目解析，具体如下：

题目描述

题目等级：容易

知识点：贪心

查看题目：过吊桥

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)

看完之后是不是有了想法了呢，快来练练手吧>>