当我在网上搜索了一大堆单调队列的文章后，
我人傻了！？
单调队列不应该很难吗？？
不应该是，像 优先队列 那样，站在 堆 的肩膀上，极尽升华吗？？？
好吧，我接受了这个事实，单调队列，本质上就是自己手搓一个函数。
然后....没了
单调队列，是一种思想！
简单的说，是用 deque 维护一个，单调递增或者递减的 长得像队列一样的玩意！
举一个简单的例子，
对于数组 [3, 1, 4, 2, 5] 和窗口大小 3，窗口从左向右滑动：
- 窗口
[3, 1, 4]：队列为[4]（最大值为 4）。 - 窗口滑动到
[1, 4, 2]：队列为[4, 2]，但 4 仍为最大值。 - 窗口滑动到
[4, 2, 5]：移除队尾比 5 小的元素2，队列为[5]，最大值为 5。
大家看到没，队列内部，从始至终，都是从大到小。
通过这种方式，单调队列能够在线性时间内解决滑动窗口最值问题，相比 暴力解法 大幅优化了效率。
当然啦，只是知道思想，肯定远远不够，上题目！
一维窗口 用来练手，
二维窗口 用来拔高！
一、滑动窗口最大值（一维）
给你一个整数数组
nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1
输出：[1]
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
class Solution { // 单调队列，就是维持deque单调递增/递减，是一种解决滑动窗口的思想，两端一起改变 // 切记，这个单调，是允许存在等于的！只要不破坏总体下滑或上升曲线就行。 public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> dq; vector<int> vec; for(int i=0; i<k; ++i){ while(!dq.empty() && dq.back()<nums[i]) dq.pop_back(); dq.push_back(nums[i]); } vec.push_back(dq.front()); for(int i=k; i<nums.size(); ++i){ if(dq.front()==nums[i-k]) dq.pop_front(); while(!dq.empty() && dq.back()<nums[i]) dq.pop_back(); dq.push_back(nums[i]); vec.push_back(dq.front()); } return vec; } };
二、子矩阵 （二维）
问题描述
给定一个 n×mn×m （nn 行 mm 列）的矩阵。设一个
矩阵的价值为其所有数中的最大值和最小值的乘积。求给定矩阵的所有大小为 a×ba×b （aa 行 bb 列）的子矩阵的价值的和。
答案可能很大，你只需要输出答案对 998244353998244353 取模后的结果。
输入格式
输入的第一行包含四个整数分别表示 nn，mm，aa，bb，相邻整数之间使用一个空格分隔。接下来
nn 行每行包含 mm 个整数，相邻整数之间使用一个空格分隔，表示矩阵中的每个数 Ai,jAi,j。
输出格式
输出一行包含一个整数表示答案。
样例输入
2 3 1 2 1 2 3 4 5 6
样例输出
58
样例说明
1×2+2×3+4×5+5×6=581×2+2×3+4×5+5×6=58。
评测用例规模与约定
对于 4040% 的评测用例，1≤n,m≤1001≤n,m≤100；
对于 7070% 的评测用例，1≤n,m≤5001≤n,m≤500；
对于所有评测用例，1≤a≤n≤10001≤a≤n≤1000，1≤b≤m≤10001≤b≤m≤1000，1≤Ai,j≤1091≤Ai,j≤109。
#include <iostream> #include <deque> using namespace std; /* 本题，直接将滑动窗口拆开，思路之巧妙 学习并锻炼到了非常多细节，比如数组应用，deque非空，deque维持下标。 */ #define ll long long const ll mod = 998244353; const int N = 1e3+5; ll matrix_max[N][N],matrix_min[N][N]; ll matrix[N][N]; deque<ll> d; void get_max(ll A[], ll B[], int len, int k){ // len遍历长度, k为区间 d.clear(); // 清理 for(int i=1; i<=len; ++i){ // 增加 if(!d.empty()&&d.front()<i-k+1) d.pop_front(); // 可能为空 while(!d.empty() && A[d.back()] < A[i] ) d.pop_back(); d.push_back(i); B[i] = A[d.front()]; } } void get_min(ll A[], ll B[], int len, int k){ d.clear(); for(int i=1; i<=len; ++i){ // 增加 if(!d.empty()&&d.front()<i-k+1) d.pop_front(); while(!d.empty()&&A[d.back()]>A[i]) d.pop_back(); d.push_back(i); B[i] = A[d.front()]; } } int main(){ int n,m,a,b; scanf("%d %d %d %d",&n,&m,&a,&b); for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) scanf("%lld",&matrix[i][j]); for(int i=1; i<=n; ++i) get_max(matrix[i],matrix_max[i],m,b); for(int i=1; i<=n; ++i) get_min(matrix[i],matrix_min[i],m,b); ll sum = 0; for(int i=b; i<=m; ++i){ // 遍历可能性 ll temp[N]; ll t_max[N],t_min[N]; for(int j=1; j<=n; ++j) temp[j]=matrix_max[j][i]; // 极限赋值 get_max(temp,t_max,n,a); for(int j=1; j<=n; ++j) temp[j]=matrix_min[j][i]; get_min(temp,t_min,n,a); for(int j=a; j<=n; ++j){ sum = (sum+(t_min[j]*t_max[j]%mod))%mod; } } cout<<sum<<endl; return 0; }
借鉴博客：
