关于单位网站建设的请示,留言页面设计模板,咸宁网站建设网络公司,网站域名的作用是什么题目链接#xff1a;https://leetcode.cn/problems/largest-local-values-in-a-matrix/
题目大意#xff1a;给出一个N*N矩阵#xff0c;要求做池化操作#xff0c;选出每个3*3矩阵的最大值#xff0c;返回一个(N-2)*(N-2)矩阵
思路#xff1a;这是个简单题#xff0c…题目链接https://leetcode.cn/problems/largest-local-values-in-a-matrix/
题目大意给出一个N*N矩阵要求做池化操作选出每个3*3矩阵的最大值返回一个(N-2)*(N-2)矩阵
思路这是个简单题虽然可以暴力做但当矩阵很大并且窗口比3*3更大时会有很多重复操作是有改进空间的。
1首先我们可以对每一行维护一个单调队列qq中【存储下标】下标对应的元素是单调递减的。想象我们要找到这一行中一个长度为3的滑动窗口保存最大值。如果扫描到的元素grid[i][j]比队尾元素大那么grid[i][j]很明显就更适合做最大值q从队尾一直弹出直到【为空】【有一个元素比grid[i][j]大】
2当j 2以后因为滑动窗口大小只有3因此可能有【弹出队首】的操作了。队首的下标对应的元素grid[i][q.front()]是最大的将其和结果对比更大的话就写入。这个过程要遍历三行k从i-2到i的过程因此用max()函数取大。随后因为滑动窗口大小只有3若队首小于等于j-2那么弹出。
完整代码
class Solution {
public:vectorvectorint largestLocal(vectorvectorint grid) {int N grid.size();vectorvectorint ret(N-2, vectorint(N-2, 0)); for (int i 0; i N; i) {dequeint q;for (int j 0; j N; j) {while (!q.empty() grid[i][j] grid[i][q.back()]) {q.pop_back();}q.push_back(j);if (j 2) {int val grid[i][q.front()];for (int k i-2; k i; k) {if (k 0 k N-2) ret[k][j-2] max(ret[k][j-2], val);}if (q.front() j-2) q.pop_front();}}}return ret;}
};
