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同学还能在桥的一头逗留的时间。

题解

解题方法

• 比较最小值和相邻两个木板中的最大值, 取两者中的最小值

算法知识

• 贪心算法

  • 时间复杂度: n
  • 空间复杂度: 1

解题思路

题目要求

1. a[0], a[n-1]块木板断了后就无法通过了, 所以时间一定大于这两块木板的最小值
2. 可以一步走两个木板

1. 定义一个最小值min, 初始值为1000000

2. 从第a[1] 块木板开始遍历, 直到a[n-2]块木板

   • 拿相邻两块木板的最大值 和最小值min 进行比较
   • 将两者中的最小的值 赋值给 最小值min
3. 判断最小值min和a[0], a[n-1]块木板的大小, 并将三者中的最小值 赋值给 最小值min
4. 返回最小值min