队列记录最大值集合
方法一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
每次剔除确保了队列里前面都是比自己大的，队列保持递减顺序