算法筆試模拟題精解之“過吊橋”

線上程式設計介紹

阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：

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)

看完之後是不是有了想法了呢，快來練練手吧>>