假设我们有一个称为阶梯的数字列表，另一个值为k。我们目前位于第0楼梯，想爬到楼梯的最后一个索引。值stair [i]表示达到索引所需的成本，在每一回合中，我们可以一次跳1、2，...，k个楼梯。我们必须找到爬到最后楼梯的最低费用。
因此，如果输入就像阶梯= [4、11、11、3、2] k = 3，那么当我们使用阶梯[4、3、2]时，输出将为9。
为了解决这个问题，我们将按照以下步骤
q：=双头队列，并在其中插入一对（stairs [0]，0）
对于我在楼梯大小的1范围内，
从q删除最后一个元素
从q的左边删除项目
当我-q [0，1]> k时
curcost：= q [0，0] +楼梯[i]
当q不为空且curcost <= q的最后一项的第一个值时，
在q的末尾插入(curcost,i)
返回q的最后一项的第一个值
让我们看一下下面的实现以获得更好的理解
from collections import deque class Solution: def solve(self, stairs, k): q = deque([(stairs[0], 0)]) for i in range(1, len(stairs)): while i - q[0][1] > k: q.popleft() curcost = q[0][0] + stairs[i] while q and curcost <= q[-1][0]: q.pop() q.append((curcost, i)) return q[-1][0] ob = Solution()stairs = [4, 11, 11, 3, 2] k = 3 print(ob.solve(stairs, k))
[4, 11, 11, 3, 2], 3
输出结果
9