leetcode 45. 跳躍遊戲--每天刷一道leetcode算法系列！(本篇)
題目描述給定一個非負整數數組，你最初位於數組的第一個位置。數組中的每個元素代表你在該位置可以跳躍的最大長度。你的目標是使用最少的跳躍次數到達數組的最後一個位置。示例:
輸入: [2,3,1,1,4]輸出: 2解釋: 跳到最後一個位置的最小跳躍數是 2。 從下標為 0 跳到下標為 1 的位置，跳 1 步，然後跳 3 步到達數組的最後一個位置。說明:假設你總是可以到達數組的最後一個位置。
分析對於[2,3,1,1,4]來說，我們會怎麼思考。首先index=0，我們可以跳1步來到index=1，也可以跳2步到達index=2.因此跳一次我們能到達的最遠的位置為index=2.然後我們從index=1出發，最多可以跳3步，可以來到index=2，3，4. 此時已經到達末尾。流程結束。假設是[2,2,3,1,4]呢？還是一樣。首先index=0，我們可以跳1步來到index=1，也可以跳2步到達index=2.因此跳一次我們能到達的最遠的位置為index=2.然後我們從index=1出發，最多可以跳2步，可以來到index=2，3。我們從index=2出發的話，最遠跳3步，可以到達位置3，4，5.
總結一下：解決這個問題，我們需要知道上次能到達的位置，作為這一次的起點。然後需要知道此次能到達的最遠的位置，作為下一次的起點
[2, 3,1, 1,2,2,1][2,3, 1,1,2, 2,1][2,3,1,1,2, 2,1]
將數組分成三段，最左邊，已經到達的位置。中間，此次可以到達的位置。右邊，本次不能到達的位置。對於數組[2, 3,1, 1,2,2,1]。第一步可以到達index=1或者index=2.但是如果調到index=1的話顯然下次可以跳的更遠。因此第一步跳到index=1的位置。變成[2,3,1,1,2, 2,1]。第二次可以到達index=2，3，4。顯然跳到index=4的話，下次可以跳的更遠。此時變成[2,3,1,1,2, 2,1 ]。此時一次跳2步到達最右端。總結一下規律，我們在跳的時候會考慮到下一步。根據下一步能跳的最遠的貪心策略，來進行每一步的選擇。
用變量right表示本次能到達的最遠的位置。用變量maxPos表示下次能到達的最遠的位置。則在本位置到right此輪循環中maxPos的變化規律為max(maxPos,nums[i] + i);
代碼public int jump(int[] nums) { int cnt = 0; if (nums == null || nums.length == 0) { return cnt; } int len = nums.length; int maxPos = 0; //下次最遠能到達的位置 int right = 0; //本次次最遠能到達的位置 for (int i = 0; i < len - 1; i++) { maxPos = (nums[i] + i) > maxPos ? (nums[i] + i) : maxPos; if (i == right) { cnt++; right = maxPos; }
} return cnt; }