LeetCode c++スライドウィンドウ最大値
1036 ワード
配列numsが与えられ、kサイズのスライドウィンドウが配列の一番左側から配列の一番右側に移動する.スライドウィンドウk内の数字しか見えません.スライドウィンドウは毎回1つだけ右に移動します.
スライドウィンドウの最大値を返します.
例:
入力:nums=[1,3,−1,−3,5,3,6,7]およびk=3出力:[3,3,5,5,6,7]解釈:
スライドウィンドウの位置の最大値
[1−3−1]−3 5 3 6 7 3 1[3−1−3]5 3 6 7 3 1[−1−3 5]3 6 7 5 1 3−1[−3 5 3 3]6 7 7 5 1 3−3[5 6]7 6 6 1 3−1−3[3 6]7 6 6 1 3−3[3 7]7注意:
kは常に有効であり、1≦k≦入力配列の大きさであり、入力配列は空ではないと仮定することができます.
ステップ:
線形時間の複雑さでこの問題を解決できますか?注意:ここでqueueを押し込むのは配列の下付きです.プログラムの注釈に示すように判断する必要があるからです.
スライドウィンドウの最大値を返します.
例:
入力:nums=[1,3,−1,−3,5,3,6,7]およびk=3出力:[3,3,5,5,6,7]解釈:
スライドウィンドウの位置の最大値
[1−3−1]−3 5 3 6 7 3 1[3−1−3]5 3 6 7 3 1[−1−3 5]3 6 7 5 1 3−1[−3 5 3 3]6 7 7 5 1 3−3[5 6]7 6 6 1 3−1−3[3 6]7 6 6 1 3−3[3 7]7注意:
kは常に有効であり、1≦k≦入力配列の大きさであり、入力配列は空ではないと仮定することができます.
ステップ:
線形時間の複雑さでこの問題を解決できますか?注意:ここでqueueを押し込むのは配列の下付きです.プログラムの注釈に示すように判断する必要があるからです.
class Solution {
// : deque nums , nums 。 , , 。 >= k, , 。
public:
vector maxSlidingWindow(vector& nums, int k) {
deque q;
vector res;
for(int i=0;i=q.front())
q.pop_front();
if(i>=k-1)
res.push_back(nums[q.front()]);
}
return res;
}
};