力扣1696.跳跃游戏 VI

力扣1696.跳跃游戏 VI

递推

•   class Solution {
    public:
        int maxResult(vector<int>& nums, int k) {
            int n = nums.size();
            vector<int> f(n);
            f[0] = nums[0];
            for(int i=1;i<n;i++)
                f[i] = *max_element(f.begin() + max(i-k,0),f.begin() + i) + nums[i];
            return f[n-1];
        }
    };
  

单调队列优化

• 保证队首就是转移来源最大值的下标

•   class Solution {
    public:
        int maxResult(vector<int>& nums, int k) {
            int n = nums.size();
            vector<int> f(n);
            f[0] = nums[0];
            deque<int> q = {0};
            for(int i=1;i<n;i++)
            {
                if(q.front() < i - k)
                    q.pop_front();
                f[i] = f[q.front()] + nums[i];
                while(!q.empty() && f[i] >= f[q.back()])
                    q.pop_back();
                q.push_back(i);
            }
            return f[n-1];
        }
    };
  

原文地址：https://blog.csdn.net/Pisasama/article/details/140551155

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！