益智跳躍比賽的複雜性

Question

我的問題是特定於這裏所提出的問題： Interview puzzle: Jump Game

頂端回答聲稱，它在O(n)時間運行。它說，它可以做到這一點

，因爲每個元素需要考慮只有一次（這將被認爲是第二次可以跳過元素）

然而，只是檢查，如果我們已經考慮了元素需要每個元素一定的時間，所以應該採取O(n^2)，對不對？ O(n)考慮每個新元素，O(n)排除我們已經考慮過的元素。爲什麼不是這種情況？

Answer 1

如果您已經考慮一個特定的元素不需要檢查，你只需要跟蹤指數最高的到你已經檢查，並從剛剛躍升至一個最高的V（除）直到那一點。

然後，您可以繼續從那裏檢查，比較每個新元素與以前的最大值。