239. 滑動(dòng)窗口最大值

難度困難

2356

給你一個(gè)整數(shù)數(shù)組?nums，有一個(gè)大小為?k?的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)。你只可以看到在滑動(dòng)窗口內(nèi)的?k?個(gè)數(shù)字。滑動(dòng)窗口每次只向右移動(dòng)一位。

返回?滑動(dòng)窗口中的最大值?。

?

示例 1：

輸入：nums = [1,3,-1,-3,5,3,6,7], k = 3輸出：[3,3,5,5,6,7]解釋：滑動(dòng)窗口的位置 ? ? ? ? ? ? ? ?最大值 --------------- ? ? ? ? ? ? ? ----- [1 ?3 ?-1] -3 ?5 ?3 ?6 ?7 ? ? ? 3 1 [3 ?-1 ?-3] 5 ?3 ?6 ?7 ? ? ? 3 1 ?3 [-1 ?-3 ?5] 3 ?6 ?7 ? ? ? 5 1 ?3 ?-1 [-3 ?5 ?3] 6 ?7 ? ? ? 5 1 ?3 ?-1 ?-3 [5 ?3 ?6] 7 ? ? ? 6 1 ?3 ?-1 ?-3 ?5 [3 ?6 ?7] ? ? ?7

示例 2：

輸入：nums = [1], k = 1輸出：[1]

?

提示：

• 1 <= nums.length <= 105

• -104?<= nums[i] <= 104

• 1 <= k <= nums.length

通過(guò)次數(shù)454,121提交次數(shù)914,348

class?Solution?{

private:

????class?MyQueue{

????public:

????????deque<int>?que;

????????void?pop(int?value){

????????????if(!que.empty()?&&?que.front()==value){

????????????????que.pop_front();

????????????}

????????}

????????void?push(int?value){

????????????while(!que.empty()?&&?value?>?que.back()){

????????????????que.pop_back();

????????????}

????????????que.push_back(value);

????????}

????????int?front(){

????????????return?que.front();

????????}

????};

public:

????vector<int>?maxSlidingWindow(vector<int>&?nums,?int?k)?{

????????vector<int>?res;

????????MyQueue?q;

????????for(int?i=0;i<k;i++){

????????????q.push(nums[i]);

????????}

????????res.push_back(q.front());

????????for(int?i=k;i<nums.size();i++){

????????????q.pop(nums[i-k]);

????????????q.push(nums[i]);

????????????res.push_back(q.front());

????????}

????????return?res;

????}

};

?

思路：

使用一個(gè)單調(diào)隊(duì)列來(lái)解決該問(wèn)題，單調(diào)隊(duì)列中插入時(shí)先判斷該數(shù)是否比前面的大，將小于該數(shù)的值全部pop，保證隊(duì)列的單調(diào)性，單調(diào)隊(duì)列pop時(shí)要判斷pop的數(shù)是否還存在在單調(diào)隊(duì)列中，不存在就不用pop,單調(diào)隊(duì)列front是返回最前面的一個(gè)值。

解決問(wèn)題時(shí)先將前k個(gè)數(shù)的最大值加入res中，然后循環(huán)時(shí)先將滑動(dòng)窗口的第一個(gè)數(shù)pop掉（如果它還在單調(diào)序列里的話），然后加入新的值，這里就是窗口的滑動(dòng)，然后再將隊(duì)列中的front加入到res中，最后返回res。