【滑动窗口】【单调队列】个人练习-Leetcode-2373. Largest Local Values in a Matrix

题目链接：https://leetcode.cn/problems/largest-local-values-in-a-matrix/

题目大意：给出一个N*N矩阵，要求做池化操作，选出每个3*3矩阵的最大值，返回一个(N-2)*(N-2)矩阵

思路：这是个简单题，虽然可以暴力做，但当矩阵很大并且窗口比3*3更大时会有很多重复操作，是有改进空间的。

（1）首先我们可以对每一行维护一个单调队列q，q中【存储下标】，下标对应的元素是单调递减的。想象我们要找到这一行中，一个长度为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:vector<vector<int>> largestLocal(vector<vector<int>>& grid) {int N = grid.size();vector<vector<int>> ret(N-2, vector<int>(N-2, 0));   for (int i = 0; i < N; i++) {deque<int> 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;}
};