A 最大矩形（单调栈问题）

题目

给一个直方图，求直方图中的最大矩形的面积。例如，下面这个图片中直方图的高度从左到右分别是2, 1, 4, 5, 1, 3, 3, 他们的宽都是1，其中最大的矩形是阴影部分。

Input

输入包含多组数据。每组数据用一个整数n来表示直方图中小矩形的个数，你可以假定1 <= n <= 100000. 然后接下来n个整数h1, …, hn, 满足 0 <= hi <= 1000000000. 这些数字表示直方图中从左到右每个小矩形的高度，每个小矩形的宽度为1。 测试数据以0结尾。

Output

对于每组测试数据输出一行一个整数表示答案。

Example

Sample Input
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
Sample Output
8
4000

思路

• 首先先维护一个单调递减栈，栈中存放每个矩形的下标，用数组r代表每个矩形向右扩展的最远距离，从左到右依次遍历每个矩形，当栈不为空且当前元素小于栈顶元素时，将栈顶元素弹出，r[Right.top()]=i-1（注意是i-1，而非i），反之，将该元素压入栈中，遍历完后，栈中剩余的元素均能扩展到最右端，即r[]=n;
• 将所有矩形反向，操作同（1），但l[Left.top()]=i+1，遍历完后，栈中剩余的元素均能扩展到最左端，即l[]=1;
• max（(r[i]-l[i])×h[i]）即为答案

总结

（1）单调栈：栈内元素自栈顶到栈底满足单调性

• 实现（增）：若栈为空或栈顶元素大于入栈元素，则入栈；否则，将不满足条件得栈顶元素全部弹出后，再入栈。
• 时间复杂度线性
• 单调递增栈可以找到往左/往右第一个比当前元素大的元素
• 单调递减栈可以找到往左/往右第一个比当前元素小的元素
• 可以求得以当前元素为最值得最大区间

（2）容易出错的点

• 由于读入的是多组数据，因此在每次读入前都要清空两个栈
• 更新l和r两个数组时，一定要注意存的是i+1还是i-1
• 记得遍历完后，对栈中剩余元素更新l/r。

实现代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;long long int h[100005];
long long int l[100005];
long long int r[100005];
long long int res=0;
stack<long long int>Right;
stack<long long int>Left;
int main()
{int n;while(scanf("%d",&n)&&n!=0){res=0;while(!Right.empty()){Right.pop();}while(!Left.empty()){Left.pop();}for(int i=1;i<=n;i++){scanf("%lld",&h[i]);l[i]=1;r[i]=n;}for(int i=1;i<=n;i++){while(!Right.empty()&&h[Right.top()]>h[i]){r[Right.top()]=i-1;Right.pop();}Right.push(i);}for(int i=n;i>=1;i--){while(!Left.empty()&&h[Left.top()]>h[i]){l[Left.top()]=i+1;Left.pop();}Left.push(i);}for(int i=1;i<=n;i++){long long int cur=h[i]*(r[i]-l[i]+1);//cout<<"i="<<i<<" "<<"area="<<cur<<endl;res=max(res,cur);}printf("%lld\n",res);}return 0;
}

B TT’s Magic Cat（前缀和与差分）

题目

长度为n的数组，一共q次操作，每次操作给出L，R，c，表示区间[L，R]中每个数均加上c，求q次操作结束后，数组中各个元素值。

Input

第一行：n，q（1≤n，q≤2e5）
第二行：数组元素a1,a2……an(-1e6≤ai≤1e6)
q行，每行：l，r，c（1≤l≤r≤n，-1e5≤c≤1e5）

Output

进行q次操作后，所有元素的值

Example

Input
4 2
-3 6 8 4
4 4 -2
3 3 1
Output
-3 6 9 2
Input
2 1
5 -2
1 2 4
Output
9 2
Input
1 2
0
1 1 -8
1 1 -6
Output
-14

思路

• 暴力做法，超时
• 将原数组转化为差分数组，即b[1]=a[1]，b[i]=a[i]=a[i-1]
• 将区间修改转变为单点修改，即a[l,r]+=c → b[l]+=c，b[r+1]-=c
• 对b数组求前缀和，即res[1]=b[1]，res[i]=res[i-1]+b[i]

总结

• 前缀和：快速求取某一区域和，时间复杂度为O(1)
• 差分：将区间修改转化为单点修改，降低时间复杂度
• 容易出错的点：
  • 数据较多，使用scanf读入，避免超时
  • 采用long long存储，防止溢出

实现代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;long long int a[200005];
long long int b[200005];
long long int res[200005];
int main()
{int n,q;cin>>n>>q;int l,r,c;for(int i=1;i<=n;i++)scanf("%lld",&a[i]);b[1]=a[1];for(int i=2;i<=n;i++)b[i]=a[i]-a[i-1];for(int i=0;i<q;i++){scanf("%d%d%d",&l,&r,&c);b[l]+=c;b[r+1]-=c;}res[1]=b[1];for(int i=1;i<=n;i++){res[i]=res[i-1]+b[i];}for(int i=1;i<=n;i++){cout<<res[i]<<" ";}return 0;
}

C 平衡字符串（尺取）

题目

一个长度为 n 的字符串 s，其中仅包含 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符。

如果四种字符在字符串中出现次数均为 n/4，则其为一个平衡字符串。

现可以将 s 中连续的一段子串替换成相同长度的只包含那四个字符的任意字符串，使其变为一个平衡字符串，问替换子串的最小长度?

如果 s 已经平衡则输出0。

Input

一行字符表示给定的字符串s

Output

一个整数表示答案

Example

Input
QWER
Output
0Input
QQWE
Output
1Input
QQQW
Output
2Input
QQQQ
Output
3

思路

• 所求解答案为一个连续区间，且区间左右端点有明确方向，因此可以使用尺取法
• 用sum1，sum2，sum3，sum4分别记录不包含区间[L，R]这一段时，字符A，B，C，D的个数
• 先通过替换使4类字符数量一致，再判断剩余空间位置是否为4的倍数
• MAX=max（sum1，sum2，sum3，sum4）
• TOTAL=R-L-1
• FREE=TOTAL-（4*MAX-sum1-sum2-sum3-sum4）
• 若FREE≥0且为4的倍数，则满足要求，令L++，寻找更小区间；否则，则令R++，寻找满足要求的区间

总结

• 尺取法适用于：
  - 所求答案为一个连续区间
  - 区间左右端点移动有明确方向

实现代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;int sum1=0,sum2=0,sum3=0,sum4=0;int main()
{string s;cin>>s;int len=s.size();int l=0,r=0;int free=0;int total=0;int ans=len;for(int i=0;i<len;i++){if(s[i]=='Q') sum1++;if(s[i]=='W') sum2++;if(s[i]=='E') sum3++;if(s[i]=='R') sum4++;}if((sum1==len/4)&&(sum2==len/4)&&(sum3==len/4)&&(sum4==len/4)){cout<<"0"<<endl;return 0;} if(s[0]=='Q') sum1--;if(s[0]=='W') sum2--;if(s[0]=='E') sum3--;if(s[0]=='R') sum4--;while(l<len&&r<len){int m=max(max(sum1,sum2),max(sum3,sum4));total=r-l+1;free=total-(4*m-sum1-sum2-sum3-sum4);if(free>=0&&free%4==0){ans=min(ans,total);if(l==r){r++;if(s[r]=='Q') sum1--;if(s[r]=='W') sum2--;if(s[r]=='E') sum3--;if(s[r]=='R') sum4--;if(s[l]=='Q') sum1++;if(s[l]=='W') sum2++;if(s[l]=='E') sum3++;if(s[l]=='R') sum4++;l++;}else{if(s[l]=='Q') sum1++;if(s[l]=='W') sum2++;if(s[l]=='E') sum3++;if(s[l]=='R') sum4++;l++;								}}else{r++;if(s[r]=='Q') sum1--;if(s[r]=='W') sum2--;if(s[r]=='E') sum3--;if(s[r]=='R') sum4--;			}}cout<<ans<<endl;return 0;
}

D 滑动窗口（单调队列）

题目

ZJM 有一个长度为 n 的数列和一个大小为 k 的窗口, 窗口可以在数列上来回移动. 现在 ZJM 想知道在窗口从左往右滑的时候，每次窗口内数的最大值和最小值分别是多少. 例如：
数列是 [1 3 -1 -3 5 3 6 7], 其中 k 等于 3.

Input

输入有两行。第一行两个整数n和k分别表示数列的长度和滑动窗口的大小，1<=k<=n<=1000000。第二行有n个整数表示ZJM的数列。

Output

输出有两行。第一行输出滑动窗口在从左到右的每个位置时，滑动窗口中的最小值。第二行是最大值。

Example

Sample Input
8 3
1 3 -1 -3 5 3 6 7
Sample Output
-1 -3 -3 -3 3 3
3 3 5 5 6 7

思路

• 首先维护一个单调递增的队列。队列中存储的是数组下标，将前k-1个元素插入到队列中，并维护队列的单调性；然后依次遍历k~n号元素，在保证单调性的前提下，维护窗口大小，即判断当前的窗口大小是否＞k，若大于，则删除队首元素，然后将队首元素保存为Min[i]
• 再维护一个单调递减的队列，操作同上，将结果保存为Max[i]

总结

• 单调栈与单调队列的区别
  • 单调栈只维护一端，单调队列维护两端
  • 单调栈通常维护全局的单调性，而单调队列是局部
  • 单调栈大小没有上限，而单调队列通常有大小限制

G++不知道为什么超时了，而C++AC了(ㄒoㄒ)~~

实现代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<deque>
using namespace std;int Max[1000005];
int Min[1000005];
int a[1000005];
deque<int>mmax;
deque<int>mmin;int main()
{int n,k;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=n;i++){while(!mmin.empty()&&a[mmin.back()]>a[i]){mmin.pop_back();}mmin.push_back(i);while(!mmin.empty()&&(i-mmin.front())>=k){mmin.pop_front();}Min[i]=mmin.front();}for(int i=1;i<=n;i++){while(!mmax.empty()&&a[mmax.back()]<a[i]){mmax.pop_back();}mmax.push_back(i);while(!mmax.empty()&&(i-mmax.front())>=k){mmax.pop_front();}Max[i]=mmax.front();}for(int i=k;i<=n;i++) {printf("%d ",a[Min[i]]);}printf("\n");for(int i=k;i<=n;i++){printf("%d ",a[Max[i]]);}return 0;
}