今天是LeetCode系列的第25篇文章，今天我們一起來看的是LeetCode的第45題，Jump Game II。

有同學後台留言問我說，我每次寫文章的題目是怎麼選的，很簡單基本上是按照順序選擇Medium和Hard難度，然後會根據題目內容以及評價過濾掉一些不太靠譜或者是比較變態沒有意思的題。

這些題當然會比Easy難度的要難上一點，但是並不是高不可攀的。至少如果你熟悉程式語言，然後會一點基礎演算法的話，就可以嘗試了，我個人覺得不是很高的門檻。

好了，我們回到正題。

今天這題的題目蠻有意思，它是說給定我們一個非負整數的數組。讓我們把這個數組想像成一個大富翁里的那種長條形的地圖。數組當中的數字表示這個位置向前最多能前進的距離。現在我們從數組0號位置開始移動，請問至少需要移動多少步可以走到數組的結尾？

搜索

我拿到題目的第一反應就是搜索，因為感覺貪心是不可以的。我們把數組當中每個位置的數字稱為前進能力，我們當下能達到的最遠的位置前進能力可能很差，所以貪心能夠達到最遠的位置並不可行，舉個例子：

[3, 1, 5, 1, 4, 2]

如果我們從0開始的時候走到3的話，由於3的前進能力很小，所以我們需要3步才能走完數組。但是如果我們一開始不走滿3，而是走到2的話，我們只需要兩步就可以完成。所以貪心是有反例的，我們不能簡單地來貪心。而且這題的狀態轉移十分明顯，幾乎是裸的順推。那麼我們只需要搜就完事了，由於這是一個求解最優的問題，所以我們應該使用寬度優先搜索。

這個程式碼我想應該很好寫，我們信手拈來：

class Solution:
    def jump(self, nums: List[int]) -> int:
        import queue
        n = len(nums)
        que = queue.Queue()
        que.put((0, 0))
        while not que.empty():
            pos, step = que.get()
            if pos >= n-1:
                return step
            for i in range(pos, min(n, pos+nums[pos] + 1)):
                que.put((i, step+1))

但是顯然這麼交上去是一定會gg的，想想也知道，我們遍歷轉移狀態的這個for-loop看起來就很恐怖，數組當中的狀態很有可能出現重複，那麼必然會出現大量的冗餘。所以我們需要加上一些剪枝，由於我們使用的是寬度優先搜索，所以所有狀態第一次在隊列當中彈出的時候就是最優解，不可能同樣的位置，我多走幾步會達到更優的結果，所以我們可以放心地把之前出現過的位置全部標記起來，阻止重複遍歷：

class Solution:
    def jump(self, nums: List[int]) -> int:
        import queue
        n = len(nums)
        que = queue.Queue()
        que.put((0, 0))
        visited = set()
        while not que.empty():
            pos, step = que.get()
            if pos >= n-1:
                return step
            
            for i in range(pos, min(n, pos+nums[pos] + 1)):
                # 如果已經入過隊列了則跳過
                if i in visited:
                    continue
                que.put((i, step+1))
                visited.add(i)

很遺憾，雖然我們加上了優化，但是還是會被卡掉。所以還需要繼續優化，我們來分析一下會超時的原因很簡單，雖然我們通過標記排除了重複進入隊列的情況。但是for循環本身的計算量可能就很大，尤其在數組當中存在大量前進能力很大的位置的時候。舉個例子，比如我們超時的樣例：

[25000,24999,24998,24997,24996,24995,24994…]

可以看到，這個數組的前進能力都很大，我們會大量地重複遍歷，這個才是計算量的根源。所以我們要避免循環重複的部分，有辦法解決嗎？

當然是有的，我們來分析一下問題，對於某一個位置x而言，它的前進能力是m。那麼它可以達到的最遠距離是x + m，這是顯然的，但是很有可能從x到x+m的區間當中已經有一部分被加入隊列了。所以當我們從x向x+m遍歷的時候，必然會重複遍歷一部分已經在隊列當中的狀態。那怎麼解決呢？

其實很簡單，我們只需要把遍歷的順序倒過來就好了。也就是說我們從x+m向x反向遍歷，當我們遇到一個狀態已經在隊列當中的時候，就可以break了，沒必要繼續往下了。因為後面的狀態肯定已經遍歷過了。

這個時候程式碼如下：

class Solution:
    def jump(self, nums: List[int]) -> int:
        import queue
        n = len(nums)
        que = queue.Queue()
        que.put((0, 0))
        visited = set()
        while not que.empty():
            pos, step = que.get()
            if pos >= n-1:
                return step
            
            # 倒敘遍歷
            for i in range(min(n-1, pos+nums[pos]), pos, -1):
                # 當遇到已經遍歷過的元素的時候直接break
                if i in visited:
                    break
                que.put((i, step+1))
                visited.add(i)

除了上面的方法之外，我們還可以想到一種優化，我們可以使用優先隊列對隊列當中的元素進行排列，將潛力比較大的元素排在前面，而將潛力差的排在後面。但是你會發現如果我們把前進能力當做是潛力或者是所處的位置當做潛力都有反例，因為位置靠前的可能前進能力很差，但是前進能力比較好的，又可能位置靠後。有沒有兩全其美的辦法呢？

當然是有的，方法也很簡單，我們把兩者相加，也就是位置加上它的前進能力當做這個位置的潛力。也可以認為是最遠能夠移動到的位置當做是潛力，這樣我們每次都挑選出其中潛力最好的進行迭代，從而保證我們可以最快地找到答案。

class Solution:
    def jump(self, nums: List[int]) -> int:
        import queue
        n = len(nums)
        # 使用優先隊列
        que = queue.PriorityQueue()
        que.put((0, 0, 0))
        visited = set()
        while not que.empty():
            _, pos, step = que.get()
            if pos >= n-1:
                return step
            
            # 倒敘遍歷
            for i in range(min(n-1, pos+nums[pos]), pos, -1):
                if i in visited:
                    break
                # 由於優先隊列是默認元素小的排在前面，所以加上負號
                que.put((-i - nums[i] ,i, step+1))
                visited.add(i)

這種方法也是可以AC的，耗時比上一種方法略小。

貪心

不知道大家在寫完上面這串程式碼之後有什麼感覺，我最大的感覺不是成就感，而是覺得奇怪，就好像總覺得有哪裡不太對勁，但是又不知道到底是哪裡不對。

後來我想了很久，終於想明白了。不對的地方在於既然我們已經想到了這麼具體的策略來優化搜索，我們為什麼還要用搜索呢？因為我們沒必要維護狀態了，直接貪心不行嗎？

在正常的bfs搜索當中，我們是一層一層地遍歷狀態的，每次遍歷的都是搜索樹上同樣深度的節點。只有某一個深度的節點都遍歷結束了，我們才會遍歷下一個深度的節點。但是現在使用了優先隊列之後，我們打破了這個限制，也就是說我們拿到的狀態根本不知道是來源於哪一個深度的。而從這個題目的題意來看，潛力大的排在前面，會使得一開始潛力小的狀態一直得不到迭代，沉積在隊列的底部。

既然如此，我們為什麼還要用隊列來存儲呢，直接維護最大的潛力值不就可以了？

解釋一下上面這段話的意思，在當前問題當中，由於我們可以走的距離是連續的。我們可以維護一個當前步數能夠移動的範圍，舉個例子，比如nums[0]=10，也就是說從0開始，一直到10的區間都是我們可以移動的。對於這個區間里的每一個x來說，它可以移動的範圍就是[x, x+nums[x]]。所以我們可以得到x+nums[x]的集合，這裡面最大的那個，就是下一步我們能夠移動的範圍。也就是說第二步的移動範圍就是[11, max(x+nums[x])]。我們不停地迭代，當能夠達到的最遠位置大於或等於數組長度的時候，就表示遍歷結束了。

如果還不明白，我們來看下下面這張圖：

rangeI表示第一步能夠移動到的範圍，顯然由於我們起始位置是0，所以這個範圍就是[0, nums[0]]。等於rangeI當中的每一個位置都有一個潛力值，其實就是它能達到的最遠的距離。對於rangeI當中的每一個位置的潛力值而言，它們顯然有一個最大值，我們假設最大值的下標是x，它的潛力值就是x+nums[x]。那麼我們就可以得到rangeII的範圍是[nums[0]+1, x+nums[x]]。我們只需要在遍歷rangeI的時候記錄下這個x就可以得到rangeII的範圍，我們重複以上過程迭代就行了。

這個思路理解了之後，程式碼就很好寫了：

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        start, end = 0, nums[0]
        step = 1
        if n == 1:
            return 0
        while end < n-1:
            maxi, idx = 0, 0
            # 維護下一個區間
            for i in range(start, end+1):
                if i + nums[i] > maxi:
                    maxi, idx = i + nums[i], i
            # 下一個區間的起始範圍
            start, end = end+1, maxi
            step += 1
        return step

只有短短十來行，我們就解出了一個LeetCode當中的難題。一般來說都是我們先試著用貪心，然後發現不行，再換演算法用搜索，而這道題剛好相反，我們是先想到搜索的解法，然後一點一點推導出了貪心。我想如果你能把上面思路推導的過程全部理解清楚，一定可以對這兩種演算法都有更深的感悟。當然，也有些大神是可以直接想到最優解的，如果做不到也沒什麼好遺憾的，只要我們勤于思考，多多理解，遲早有一天，這些問題對我們來說也不會是難事。

今天的文章就是這些，如果覺得有所收穫，請順手點個關注或者轉發吧，你們的舉手之勞對我來說很重要。