Leetcode_45. 跳跃游戏 II

每个位置i有一个最大跳跃距离，求最小步数从0跳到n-1。

dp[i]表示从0跳到i的最少步数，显然可以转移的状态就是从i-a[i]到i-1。
因为是最小步数，考虑用优先队列优化，再考虑到状态有范围的，所以用单调队列，及时将失效的dp状态移除。

code

class Solution {
public:
    int jump(vector<int>& nums) {
        int n=nums.size();
        vector<int> q(n,0);
        vector<int> dp(n,0);
        int l=0,r=-1;
        dp[0]=0;
        q[++r]=0;
        for(int i=1;i<n;i++){
            while(l<=r && q[l]+nums[q[l]]<i){
                l++;
            }
            dp[i]=dp[q[l]]+1;
            while(l<=r && dp[q[l]]>dp[i]){
                r--;
            }
            q[++r]=i;
        }
        return dp[n-1];
    }
};

posted @ 2020-05-11 19:38 Keane1998 阅读(158) 评论(0) 收藏举报

刷新页面返回顶部

登录后才能查看或发表评论，立即登录或者逛逛博客园首页

【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！
【推荐】国内首个AI IDE，深度理解中文开发场景，立即下载体验Trae
【推荐】轻量又高性能的 SSH 工具 IShell：AI 加持，快人一步

编辑推荐：
· 记录一次线上问题排查：JDK序列化问题
· 微服务之间有哪些调用方式？
· 记一次SQL隐式转换导致精度丢失问题的排查
· dotnet 9 通过 AppHostRelativeDotNet 指定自定义的运行时路径
· 如何统计不同电话号码的个数？—位图法

阅读排行：
· EF Core 10 现已支持 LeftJoin 和 RightJoin 运算符查询了！
· Python 3.14 t-string 要来了，它与 f-string 有何不同？
· C#网络编程(一)----应用层/传输层
· Promise 这个新 API 真香！
· 记录一次线上问题排查：JDK序列化问题