单调队列【C/C++】

当我在网上搜索了一大堆单调队列的文章后，

我人傻了！？

单调队列不应该很难吗？？

不应该是，像优先队列那样，站在堆的肩膀上，极尽升华吗？？？

好吧，我接受了这个事实，单调队列，本质上就是自己手搓一个函数。

然后....没了

单调队列，是一种思想！

简单的说，是用 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       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7
示例 2：
输入：nums = [1], k = 1
输出：[1]
提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= 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;
}

借鉴博客：

1、算法学习笔记(66): 单调队列

2、【C++】单调队列详解