y1,y2总复习笔记8 2026.7.22

好吧今天没有最小生成树的prim一单调栈维护一个栈使栈内所有元素严格保持单调递增或单调递减实现过程初始化空栈栈中推荐存下标而非数值方便计算距离、边界循环遍历数组每一个下标 i while 栈不为空 且 当前元素破坏栈单调性 弹出栈顶元素 top 此时 栈顶的目标边界就是 i记录答案将当前下标 i 压入栈模板例题找每个数字左侧第一个更小的数字按照实现过程得到代码如下#includebits/stdc.h using namespace std; const int N1e55; stackint st; int a[N]; int main(){ int n; cinn; for(int i1;in;i){ cina[i]; } for(int i1;in;i){ while(!st.empty()a[st.top()]a[i]){ st.pop(); } if(st.empty()) cout-1 ; else couta[st.top()] ; st.push(i); } }真正的例题区间最小值问题给出正整数n和一个长度为n的数列要求找出一个子区间使这个子区间的数字之和乘上子区间中的最小值最大。我们的思路如下枚举区间左右端点搞贪心肯定不行1≤n≤10^5​​,0≤a[i]≤10^​6​​那我们的思路转移到最小值上枚举每一个点作为一个区间的最小值再反推求这个区间的左端点和右端点那区间端点怎么求呢一个数要想成为这个区间的最小值显然这个区间里不能再有比它小的数在它左边找第一个比它小的那这个第一个比它小的右边自然都比它大了在它右边找第一个比它小的那这个第一个比它小的左边自然都比它大了这样就得到了一个区间而找第一个比它小的数的过程我们考虑单调栈区间和直接采用前缀和代码如下long long 警告1-1警告#includebits/stdc.h using namespace std; const int N1e55; stackint st; int a[N],L[N],R[N],sum[N]; int main(){ int n; cinn; for(int i1;in;i){ cina[i]; sum[i]sum[i-1]a[i]; } for(int i1;in;i){ while(!st.empty()a[st.top()]a[i]){//留大的就是找左边第一个比自己小的 st.pop(); } if(st.empty()) L[i]0; else L[i]st.top(); st.push(i); } while(!st.empty()) st.pop(); for(int in;i1;i--){ while(!st.empty()a[st.top()]a[i]){ st.pop(); } if(st.empty()) R[i]n1; else R[i]st.top(); st.push(i); } int ans-1,l,r; for(int i1;in;i){ if(ans(sum[R[i]-1]-sum[L[i]])*a[i]){ ans(sum[R[i]-1]-sum[L[i]])*a[i]; lL[i]1; rR[i]-1; } } coutans\nl r; }本来想再放一个题但是都差不多其实就这样吧二单调队列队列内元素保持单调递增 / 单调递减的双端队列叫做单调队列求解问题定长滑动窗口最大值、最小值在这其中想要的元素在队头所以想要最小值从队头到队尾单调递增想要最小值从队头到队尾单调递减删除队头的情况队头太远不在所求范围内。删除队头无论如何要把a[i]插入队尾实现过程队尾维护单调性新元素 a[i] 入队前不断把队尾不如 a[i] 优的元素弹出。以单调递减求窗口最大值为例 若 a[i]≥a[q.back()]队尾元素可以永久删除。逻辑只要 i 还在窗口里队尾这个数永远不可能成为任何窗口的最大值没有保留价值。队头剔除过期元素窗口不断右移如果队头下标 q.front()≤i−k说明已经跑出窗口左边界弹出队头。维护单调的过程若要添加的元素小于队尾元素则不断末尾出队直至队尾元素小于要添加的元素。维护长度的过程若队列长度超过规定长度则队头出队。模板滑动窗口最大值for(int i1;in;i){ while(!q.empty() a[i] a[q.back()]){ q.pop_back(); } q.push_back(i); //注意存储下标 while(q.front() i - k){ q.pop_front(); } if(i k){ couta[q.front()] ; } }回顾一下二维前缀和的二次扫描法二维前缀和的二次扫描法 假设sum[i][j]a[i][j] for(int i1;in;i){ for(int j1;jn;j){ sum[i][j]sum[i][j-1]; } } for(int i1;in;i){ for(int j1;jn;j){ sum[i][j]sum[i-1][j]; } }第一层循环对每一行求一维前缀和x-------x-------x-------此时的sum[i][x]已经累加了该行前面的所有元素sum[i][j]只代表第 i 行前 j 个元素总和还不是二维前缀和。第二层循环对每一列求一维前缀和现在sum[i][j]本身已经是第 i 行横向前缀和 再纵向累加上面一行同列的值。就得到了二维前缀和注意查询x1,y2)(x2,y2)子矩形anssum[x2​][y2​]−sum[x1​−1][y2​]−sum[x2​][y1​−1]sum[x1​−1][y1​−1]例题来了理想的正方形有一个n×m的整数组成的矩阵现请你从中找出一个k×k的正方形区域使得该区域所有数中的最大值和最小值的差最小。与我们的二次扫描前缀和同源先对每一行用单调队列求出每行内、长度为 k 的滑动窗口最大值、最小值 得到两个新矩阵row_max[i][j]、row_min[i][j]第 i 行区间的最大值。再对row_max的每一列做单调队列窗口大小 k 得到sq_max[x][y]左上角对应 (x-k1,y-k1) 的正方形最大值。同理对row_min每一列单调队列得到每个正方形最小值sq_min[x][y]。遍历所有正方形求。思路大概是这样的代码如下#includebits/stdc.h #define ll long long const int N1e35; using namespace std; int n,m,k,a[N][N],r_max[N][N],r_min[N][N],ans0x7fffffff; dequeint Max,Min; int main(){ scanf(%d%d%d,n,m,k); for(int i1;in;i){ for(int j1;jm;j){ scanf(%d,a[i][j]); } } for(int i1;in;i){ for(int j1;jm;j){ while(!Max.empty()Max.front()kj){ Max.pop_front(); } while(!Max.empty()a[i][Max.back()]a[i][j]){ Max.pop_back(); } Max.push_back(j); while(!Min.empty()Min.front()kj){ Min.pop_front(); } while(!Min.empty()a[i][Min.back()]a[i][j]){ Min.pop_back(); } Min.push_back(j); if(jk){ r_min[i][j]a[i][Min.front()]; r_max[i][j]a[i][Max.front()]; } } while(!Max.empty()) Max.pop_front(); while(!Min.empty()) Min.pop_front(); } for(int jk;jm;j){ for(int i1;in;i){ while(!Max.empty()Max.front()ki){ Max.pop_front(); } while(!Max.empty()r_max[Max.back()][j]r_max[i][j]){ Max.pop_back(); } Max.push_back(i); while(!Min.empty()Min.front()ki){ Min.pop_front(); } while(!Min.empty()r_min[Min.back()][j]r_min[i][j]){ Min.pop_back(); } Min.push_back(i); if(ik){ ansmin(ans,r_max[Max.front()][j]-r_min[Min.front()][j]); } } while(!Max.empty()) Max.pop_front(); while(!Min.empty()) Min.pop_front(); } coutans; }