前往
大廳
主題

[leetcode]1340. Jump Game V

♙♲⚙\~O_O~/⚙♲♙ | 2021-08-09 12:00:13 | 巴幣 4 | 人氣 140

題目: 1340. Jump Game V
難度: Hard
目前下列解法的時間複雜度: O(n*lg(n)) // 卡sort


題目說明

給你一排 n 個柱子,以及每根柱子的高度。以及一個距離 d 。
你將選擇從一根柱子開始。
假設你現在在A柱,你將跳向另一根B柱,A,B兩柱的距離<=d,且B柱比A柱矮、A,B兩柱當中沒有任何一根柱子的高度>=A柱的高度。反覆循環直到不能再跳。
問: 你最多可以踩過幾根柱子。


解法

1. 先 O(n) 2次(左+右)對每根柱子拿最靠近它又比他高的柱子。
2. 接著建一張次數表(size=柱子數),初始值皆為1。
3. 然後從最矮柱子走到最高柱子,每根柱子用步驟 1. 做出來的東西往左右各走1次,更新步驟2的次數表。(+1,取大)
4. 從表中拿最大的值回傳。


source code

創作回應

相關創作

更多創作