reLeetCode 热题 100- 239. 滑动窗口最大值 队列

 

 

 队列记录最大值集合

方法一1 枚举 速度嘛 n*k

 

方法2 map 记录频次 通过速度慢

 

方法3 队列记录当前最大值 最快

 

 

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> result; if(nums.size()==0 || k==0){return result;    }deque<int> result_index; // 4 3 1      4 2 3-> 4 2-> 4 3for(int i=0;i<k;i++){while(!result_index.empty() && nums[i]>nums[result_index.back()]){result_index.pop_back();}result_index.push_back(i);}result.push_back(nums[result_index.front()]);for(auto p:result_index){cout<< nums[p]<< " " ;}cout<< endl ;for(int i=k;i<nums.size();i++){// 抛弃上一个数据 如果上一个数据刚好是最大的if(!result_index.empty() && result_index.front()==i-k){result_index.pop_front();}// 5 3 4  - 5 4while(!result_index.empty() && nums[i]>nums[result_index.back()]){result_index.pop_back();}result_index.push_back(i);result.push_back(nums[result_index.front()]);for(auto p:result_index){cout<< nums[p]<< " " ;}cout<< endl ;}return result;  }
};

　　队列 k=3 

 5 4 3 （4）-》剔除 小于当前值  5 4 剔除目前最大的索引为n-k  4 ，插入 4 4 最大 4

每次剔除确保了队列里前面都是比自己大的，队列保持递减顺序