45. 跳躍游戲 II
題目來(lái)源：https://leetcode-cn.com/problems/jump-game-ii
題目
給定一個(gè)非負(fù)整數(shù)數(shù)組怪嫌，你最初位于數(shù)組的第一個(gè)位置尝偎。
數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長(zhǎng)度晚树。
你的目標(biāo)是使用最少的跳躍次數(shù)到達(dá)數(shù)組的最后一個(gè)位置。
示例:
輸入: [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個(gè)位置的最小跳躍數(shù)是 2。
從下標(biāo)為 0 跳到下標(biāo)為 1 的位置，跳 1 步咆耿，然后跳 3 步到達(dá)數(shù)組的最后一個(gè)位置。
說(shuō)明:
- 假設(shè)你總是可以到達(dá)數(shù)組的最后一個(gè)位置爹橱。
解題思路
思路：貪婪算法
首先票灰，先注意題意的說(shuō)明部分【假設(shè)你總是可以到達(dá)數(shù)組的最后一個(gè)位置】。這里只需要考慮宅荤，題目中所給出的數(shù)組，是一定能夠到達(dá)數(shù)組的最后一個(gè)位置浸策。
這題要求與之前 55. 跳躍游戲 并不相同冯键，55 題要求的返回是否能夠到達(dá)最后一個(gè)位置。如果用 55 題的反例來(lái)論證本題意義不大庸汗，若覺(jué)得有必要惫确，也可以在無(wú)法到達(dá)時(shí)返回特定的值用以標(biāo)記，例如 0蚯舱。
現(xiàn)在考慮如何去求得到達(dá)最后位置的最小跳躍次數(shù)改化？
在這里，我們考慮使用正向去找可到達(dá)的最遠(yuǎn)位置枉昏。這里以示例 1 為例陈肛，[2,3,1,1,4]，索引為 0 的位置兄裂，這里元素值為 2句旱，表示該位置能夠跳躍到達(dá)的位置為后續(xù)兩個(gè)位置，如下圖所示紅色部分：
在這里晰奖，索引為 1 的位置中谈撒，元素值值為 3，表示能夠后續(xù)三個(gè)位置匾南，能到達(dá)最遠(yuǎn)的位置為索引 4啃匿，這里已經(jīng)到達(dá)末尾位置。而索引 2 的位置中蛆楞，值為 1溯乒，這里只能跳躍到索引為 3 的位置。這里顯然從索引 1 的位置跳躍能到達(dá)更遠(yuǎn)的位置臊岸。
假設(shè)數(shù)組后續(xù)還未到達(dá)末尾橙数，，現(xiàn)在選擇先跳到索引 1 的位置帅戒，上面說(shuō)能夠在該位置能跳躍到后續(xù)三個(gè)位置灯帮，這里如何選擇落腳的地方崖技？跟上面討論的一樣，在每個(gè)可到達(dá)的位置钟哥，判斷各自能夠跳躍的最遠(yuǎn)的位置迎献。
現(xiàn)在位置在索引 1 的位置上面，如下圖所示腻贰，3 個(gè)紅色部分就是索引 1 這個(gè)位置能夠跳躍的選擇吁恍，而跳到索引 4 的位置，能夠跳躍更遠(yuǎn)的位置播演，所以此處是當(dāng)前最好的落腳點(diǎn)冀瓦。
現(xiàn)在考慮如何實(shí)現(xiàn)？我們可以維護(hù)這個(gè)可到達(dá)的最遠(yuǎn)位置写烤，作為邊界翼闽。當(dāng)我們正向遍歷的時(shí)候，當(dāng)?shù)竭_(dá)邊界時(shí)洲炊，就更新這個(gè)邊界感局，相應(yīng)的跳躍次數(shù)加 1。
這里需要注意一點(diǎn)暂衡，我們從正向遍歷的時(shí)候询微，不用遍歷最后一個(gè)位置。根據(jù)上面的說(shuō)明知道狂巢，這里一定會(huì)到達(dá)最后一個(gè)位置撑毛。那么前面所述的需要維護(hù)的這個(gè)邊界，一定是大于或等于最后那個(gè)位置的唧领。如果邊界剛好就在最后的位置時(shí)代态，按照前所述的到達(dá)邊界時(shí)，更新邊界疹吃，跳躍次數(shù)加 1 的邏輯蹦疑，這里會(huì)增加不必要的跳躍次數(shù)。所以不考慮訪問(wèn)這個(gè)最后的位置萨驶。
具體的代碼實(shí)現(xiàn)如下歉摧。
代碼實(shí)現(xiàn)
class Solution:
def jump(self, nums: List[int]) -> int:
# 定義最遠(yuǎn)位置，邊界腔呜，步數(shù)
max_pos = 0
end = 0
steps = 0
for i in range(len(nums) - 1):
# 獲取最遠(yuǎn)可到達(dá)位置
max_pos = max(max_pos, i + nums[i])
# 到達(dá)邊界時(shí)叁温，更新邊界
# 同時(shí)跳躍次數(shù)加 1
if i == end:
end = max_pos
steps += 1
return steps
實(shí)現(xiàn)結(jié)果
以上就是使用貪心算法，從數(shù)組開(kāi)始正向遍歷核畴，維護(hù)可跳躍最遠(yuǎn)的位置膝但，確定邊界，到達(dá)邊界時(shí)谤草，更新邊界跟束，增加跳躍次數(shù)莺奸，進(jìn)而解決《45. 跳躍游戲 II》問(wèn)題的主要內(nèi)容。
歡迎關(guān)注微信公眾號(hào)《書(shū)所集錄》
