暴力的时间复杂度是O(nk)
vector<int> comp(vector<int> v) { vector<int> ans; for(int i = 0; i+1 < v.size(); i++) ans.push_back(max(v[i],v[i+1])); return ans; } vector<int> maxInWindows(vector<int>& num, unsigned int size) { if(size == 1) return num; vector<int> ans; for(int i = 1; i < size; i++) if(i == 1) ans = comp(num); else ans = comp(ans); return ans; }此时获取窗口中的最大值的复杂度为O(k)。 那么如何将O(k)的复杂度变为O(1)是我们该考虑的地方。 我们可以将双端队列deque作为滑动窗口。deque内部，要保证元素非严格递减，则deque[0]是当前窗口的最大值。 那么每次窗口滑动，将删除deque的内部对应的元素，添加新元素k，并将小于k的元素删除。
vector<int> maxInWindows(const vector<int>& num, unsigned int size) { if(size == 1) return num; vector<int> ans; deque<int> q;//维护每个窗口最大值的下标 if(num.size() < size || size == 0) return ans; for(int i = 0; i < size; i++){//初始化窗口 while(!q.empty() && num[i] > num[q.back()]) q.pop_back(); q.push_back(i); } for(int i = size; i < num.size(); i++){ ans.push_back(num[q.front()]);//当前窗口的最大值 while(!q.empty() && num[i] >= num[q.back()]) q.pop_back();//新添加的元素大于队列最后一个 while(!q.empty() && q.front() <= i-size) q.pop_front();//判断队首元素是否过期(在窗口外) //i-q.front()>=size ，size是无符号类型 q.push_back(i); } ans.push_back(num[q.front()]); return ans; }此时，时间复杂度为O(n)，空间复杂度为O(k).
