文章目錄

• • • 題目分析
    • 題目鏈接
    • 單調(diào)隊列板子鏈接
    • Deque知識補(bǔ)充

題目分析

題目重述：給定一個數(shù)組（有正數(shù)有負(fù)數(shù)）和一個步長k，從下標(biāo)0處開始往前跳，每次最多往前跳k步。求跳到最后一個位置，得分之和最多是多少，所謂得分指的是經(jīng)過的元素值。

數(shù)據(jù)規(guī)模： $nums[]長度10^5，k也是10^5規(guī)模$。
這是一個DP題：

狀態(tài)表示：用$f[i]$表示 從下標(biāo)0 跳到下標(biāo)i處得到的總得分

狀態(tài)轉(zhuǎn)移：$f[i]=max(f[j])+a[i],i?k\le j＜i$，j被步長k限制。

DP的時間復(fù)雜度 = 狀態(tài)種類 × 轉(zhuǎn)移的復(fù)雜度 = n ×k ，即最壞$O(n^2)$這樣的話肯定會TLE， 怎么優(yōu)化呢？ 這里對轉(zhuǎn)移進(jìn)行優(yōu)化，優(yōu)化成O(1)，那么總的復(fù)雜度O(n)，是可以過的。

下面的問題是，如何在O(1)時間內(nèi)求一個長度為k的滑動窗口的最大值。

需要用到單調(diào)隊列優(yōu)化。該單調(diào)隊列需要兩端操作，最好使用deque來維護(hù)。

雙端隊列隊頭何時維護(hù)？隊頭需要保持q隊列長度小于等于k，當(dāng)大于k的時候需要隊頭后移，即q.pop_front().

隊尾怎么維護(hù)？ 隊尾需要保證新來的元素和原隊列構(gòu)成單調(diào)關(guān)系，否則刪掉原隊列的元素直到單調(diào)為止。 求滑動窗口最大值的時候，需要維護(hù)單調(diào)遞減；求滑動窗口最小值的時候，需要維護(hù)單調(diào)遞增。

ac代碼

class Solution { public:int maxResult(vector<int>& nums, int k) {int n =nums.size();vector<int> f(n);//dp數(shù)組：f(i)表示下標(biāo)0跳到i的總和是多少 f[0]=nums[0]; // f(0)為初始值，自身權(quán)值是nums[i]deque<int> q; //使用雙端隊列來維護(hù)單調(diào)隊列(滑動窗口中最大值)q.push_back(0); // q存的是下標(biāo)，初始0存入for(int i=1;i<n;i++){ //從下標(biāo)1開始遍歷if(q.front()<i-k) q.pop_front();//劃出窗口的值移出去,保證 滑動窗口的大小f[i]=f[q.front()]+nums[i];// dp轉(zhuǎn)移方程 f(i)=max(f(j))+nums[i] while(q.size() && f[q.back()]<=f[i]) //q不空 && 小于當(dāng)前值的冗余全刪掉，求最大值，維護(hù)單調(diào)減的隊列q.pop_back();q.push_back(i); //當(dāng)前下標(biāo)壓入單調(diào)隊列q}return f[n-1];} };

題目鏈接

Leetcode1696. 跳躍游戲 VI

單調(diào)隊列板子鏈接

單調(diào)隊列板子：求滑動窗口中最大值和最小值

Deque知識補(bǔ)充

deque 從隊尾操作

deque<stirng> c; c.push_back(); c.pop_back(); //和vector 一樣

deque新增的是從隊首操作

c.push_front(); //從隊首插入一個元素 c.pop_front();//從隊首刪除一個元素

總結(jié)

以上是生活随笔為你收集整理的Leetcode1696. 跳跃游戏 VI[C++题解]：dp和单调队列求滑动窗口最值的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。