LeetCode --- 45. Jump Game II

タイトルリンク:Jump Game II
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example: Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
この問題の要求は整数配列を与え,配列要素は毎回ジャンプできる最大距離を表す.次に、初期位置は配列の最初の要素であり、最小ステップで最後の要素に到達することを目的とします.
この問題はJump Game IIであり,そのJump Gameの拡張である.
Jump Gameでは,貪欲な考え方を採用し,reach変数メンテナンスを採用することで最も遠くまで到達できる,すなわちグローバル最適解である.iに遍歴すると局所最適解はA[i]+iとなるので,このときのグローバル最適解はreachとA[i]+iの最大値であるreach=max(reach,A[i]+i)である.
この問題は、最も少ないステップ数を求めなければならない.したがってstep変数レコードの最小ステップ数を追加する必要があります.stepはいつ1を追加する必要がありますか?答えは、現在のiが前のステップの最も遠い位置を超えていることです.したがってlast変数を導入して、前のステップで到達できる最も遠い位置を記録します.reach,step,lastの初期値はいずれも0である.iまで遍歴する場合、iがlast(すなわち、前のステップで到達可能な最も遠い位置)を超えた場合、ステップ数に1(すなわちstep++)を加える必要があることを示し、lastを現在の最も遠い位置reachに更新する必要がある.全行程は1回の配列を遍歴するだけで、空間複雑度は定数である.
時間複雑度:O(n)
空間複雑度:O(1)

 1 class Solution
 2 {
 3 public:
 4     int jump(int A[], int n)
 5     {
 6         int reach = 0, last = 0, step = 0;
 7         for(int i = 0; i <= reach && i < n; ++ i)
 8         {
 9             if(i > last)
10             {
11                 ++ step;
12                 last = reach;
13             }
14             reach = max(reach, A[i] + i);
15         }
16         return reach >= n - 1 ? step : 0;
17     }
18 };

転載は出典を説明してください:LeetCode---45.Jump Game II