网信办抓好网站建设,rar在线解压缩网站,李炎辉网站建设教程,做请柬网站题目要求 思路 1.这个题是可以暴力求解的#xff0c;但是时间复杂度比较高#xff0c;因此#xff0c;这里说一个时间复杂度为O(n)的方法 2.因为这个代码是优化后的结果#xff0c;第一次写如果直接写成这样着实不容易#xff0c;因此#xff0c;我直接讲每一行的含义。…题目要求 思路 1.这个题是可以暴力求解的但是时间复杂度比较高因此这里说一个时间复杂度为O(n)的方法 2.因为这个代码是优化后的结果第一次写如果直接写成这样着实不容易因此我直接讲每一行的含义。 3.创建一个数组ans这个用来存储最终返回的最大值的结果 4.创建一个双端队列dq这个里面存储是num中元素的下标 5.首先如果dq为空那么我们先插入一个第一个元素的下标 6.第二个while循环如果新来的这个元素的值大于之前元素的值那么新来的这个值只要没出去前面的比他小的值都需要被覆盖目的就是让num[dq[i]]的值是单调递减的 6.第一个while循环用于模拟滑动窗口的左端如果该元素从左边已经滑出那么需要更新双端队列的队头 7.将满足滑动窗口中最大的值也就是存储在dq中的front的下标的值保存到ans中最后返回ans。 总结这个题代码行数虽然不多但是着实不好一次写对算是一个比较重要的题值得深思。
代码实现
class Solution {
public:vectorint maxInWindows(vectorint num, int size) {vectorint ans;dequeint dq; //用于存储下标for(int i 0; i num.size(); i){while( !dq.empty() i - dq.front() 1 size)dq.pop_front();while(!dq.empty() num[dq.back()] num[i])dq.pop_back();dq.push_back(i);if(size i size - 1)ans.push_back(num[dq.front()]);}return ans;}
};
