就是一些很神奇的數(shù)據(jù)結(jié)構(gòu)
A：最大矩形
題目：
給一個直方圖，求直方圖中的最大矩形的面積愿阐。例如亭引，下面這個圖片中直方圖的高度從左到右分別是2, 1, 4, 5, 1, 3, 3, 他們的寬都是1，其中最大的矩形是陰影部分虾啦。
input:
輸入包含多組數(shù)據(jù)翠霍。每組數(shù)據(jù)用一個整數(shù)n來表示直方圖中小矩形的個數(shù)锭吨，你可以假定1 <= n <= 100000. 然后接下來n個整數(shù)h1, …, hn, 滿足 0 <= hi <= 1000000000. 這些數(shù)字表示直方圖中從左到右每個小矩形的高度，每個小矩形的寬度為1寒匙。 測試數(shù)據(jù)以0結(jié)尾零如。
output:
對于每組測試數(shù)據(jù)輸出一行一個整數(shù)表示答案。
在矩形條里面選取最大的矩形，首先想到暴力做法的話埠况，估計必須會有O（n^2）的復(fù)雜度（每個點都找左右延申最遠） 這樣耗費不可接受耸携。所以就要用到這里的數(shù)據(jù)結(jié)構(gòu)，單調(diào)棧
所謂單調(diào)棧就是辕翰，以遞增棧為例夺衍，如果加入元素小于棧頂，入棧喜命，否則棧頂出棧沟沙，直到滿足元素小于棧頂或者棧空壁榕。
對于矩形柱矛紫，從當前向右，要使得必須大于當前的矩形柱才可以延申牌里。因此維護的是一個遞增棧颊咬，是當前元素i被pop 的時候就說明這時候要加入的這個元素比當前元素小，也就是能夠向右拓展的最大距離了牡辽。
向左拓展的距離類似喳篇，反向建立一個單增棧即可。
（說起來簡單其實需要自己稍微模擬一下）
#include<iostream>
#include<stack>
using namespace std;
const int N = 100000 + 50;
long long maxit(long long a, long long b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
int lf, rt;
int hight;
long long ans;
long long n, a[N], L[N], R[N], st[N];
int main()
{
cin >> n;
while(n!=0)
{
ans=0;
stack<long long> A;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
int i = 0;
while (i < n)
{
if (A.empty() || a[A.top()] <= a[i])
{
A.push(i);
i++;
}
else
{
int tp = A.top();
A.pop();
long long area;
if (A.empty())
{
area = a[tp] * i;
ans = maxit(ans, area);
}
else
{
area = a[tp] * (i -1- A.top());
ans = maxit(ans, area);
}
}
}
while (!A.empty())
{
long long area;
int tp = A.top();
A.pop();
if (A.empty())
{
area = a[tp] * i;
ans = maxit(ans, area);
}
else
{
area = a[tp] * (i -1-A.top());
ans = maxit(ans, area);
}
}
cout << ans << endl;
cin>>n;
//for(int i=0)
}
return 0;
}
直接用了stl态辛，據(jù)說手動模擬更簡單麸澜？
B：TT’s Magic Cat
題目：
給定一個數(shù)組，在其（l,r）區(qū)間內(nèi)的每個值都增加k奏黑，求q輪后的數(shù)組炊邦。
input:
第一行包含兩個整數(shù)n，q（1≤n熟史，q≤2?105）分別表示數(shù)組的長度和操作的輪數(shù)
第二行包含序列a的元素：整數(shù)a1馁害、a2、…以故、an（-106≤ai≤106）蜗细。
接下來是q行，每一行代表一個操作怒详。第i行包含用于第i操作的三個整數(shù)l、r和c（1≤l≤r≤n踪区，-105≤c≤105）昆烁。
output:
打印出變化后的數(shù)組
暴力：O（n^2）的時間復(fù)雜度無法接受。
所以要做的就是用新的辦法缎岗。我們用的是差分法》 那么啥是差分
（這樣/我知道手寫不是一個好習(xí)慣orz
#include<iostream>
using namespace std;
long long a[300020];
long long b[300020];
int main()
{
int m,n;
cin>>n>>m;
int lf,rt;
for(int i=0;i<n;i++)
{
scanf("%lld",&a[i]);
}
b[0]=a[0];
for(int i=1;i<n;i++)
{
b[i]=a[i]-a[i-1];
}
for(int i=0;i<m;i++)
{
int value;
scanf("%d%d%d",&lf,&rt,&value);
b[lf-1]=b[lf-1]+value;
b[rt]=b[rt]-value;
}
a[0]=b[0];
for(int i=1;i<n;i++)
{
a[i]=b[i]+a[i-1];
}
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
return 0;
}
C：平衡字符串
題目：
一個長度為 n 的字符串 s静尼，其中僅包含 ‘Q’, ‘W’, ‘E’, ‘R’ 四種字符。
如果四種字符在字符串中出現(xiàn)次數(shù)均為 n/4，則其為一個平衡字符串鼠渺。
現(xiàn)可以將 s 中連續(xù)的一段子串替換成相同長度的只包含那四個字符的任意字符串鸭巴，使其變?yōu)橐粋€平衡字符串，問替換子串的最小長度?
如果 s 已經(jīng)平衡則輸出0拦盹。
input:
一行字符表示給定的字符串s
output:
一個整數(shù)表示答案
樣例輸入：
QWER
樣例輸出：
0
樣例輸入：
QQWE
樣例輸出：
1
樣例輸入：
QQQE
樣例輸出：
2
樣例輸入：
QQQQ
樣例輸出：
3
這題要介紹的辦法是鹃祖，尺取法。簡單說就是拿著一個游標尺子去取長度普舆。
不符合條件恬口，右標右移，符合條件沼侣，左標右移祖能。當然尺取的區(qū)間需要連續(xù)。
顯然這道題符合這樣的條件蛾洛。养铸。那么剩下的就是進行統(tǒng)計了，統(tǒng)計區(qū)間外面的字母數(shù)量（首先每個字母該有幾個我們是知道的) 然后……區(qū)間內(nèi)部的字母都可以作為自由的去填補這些缺口轧膘，看看缺口能不能被補上確定是不是“符合條件”
#include<iostream>
#include<string>
#include<cstring>
#include<string.h>
using namespace std;
int a[4];
int ziyouji=0;
int bl(char c)
{
if(c=='Q') return 0;
else if(c=='W') return 1;
else if(c=='E') return 2;
else if(c=='R') return 3;
}
int minit(int a,int b)
{
if(a<b) return a;
else return b;
}
bool queren(int ll)
{
int tx=0;
for(int i=0;i<4;i++)
{
if(a[i]>ll)
{
return false;
}
tx+=ll-a[i];
}
if(tx==ziyouji)
{
return 1;
}
else
{
return 0;
}
}
int main()
{
int now;
memset(a,0,sizeof(a));
string x;
cin>>x;
int ans=x.length();
int t=x.length();
for(int i=0;i<t;i++)
{
if(x[i]=='Q') a[0]++;
else if(x[i]=='W') a[1]++;
else if(x[i]=='E') a[2]++;
else if(x[i]=='R') a[3]++;
}
int tl=t/4;
int l=0,r=0;
while(r<x.length())
{
if(queren(tl))
{
//cout<<"hello"<<l<<" "<<r<<endl;
ans=minit(ans,r-l);
a[bl(x[l])]++;
l++;
ziyouji--;
}
else
{
//cout<<"hi"<<l<<" "<<r<<endl;
a[bl(x[r])]--;
ziyouji++;
r++;
}
}
cout<<ans<<endl;
return 0;
}
D：滑動窗口
題目：
ZJM 有一個長度為 n 的數(shù)列和一個大小為 k 的窗口, 窗口可以在數(shù)列上來回移動. 現(xiàn)在 ZJM 想知道在窗口從左往右滑的時候钞螟，每次窗口內(nèi)數(shù)的最大值和最小值分別是多少. 例如：
數(shù)列是 [1 3 -1 -3 5 3 6 7], 其中 k 等于 3.
input:
輸入有兩行。第一行兩個整數(shù)n和k分別表示數(shù)列的長度和滑動窗口的大小扶供，1<=k<=n<=1000000筛圆。第二行有n個整數(shù)表示ZJM的數(shù)列。
output:
輸出有兩行椿浓。第一行輸出滑動窗口在從左到右的每個位置時太援，滑動窗口中的最小值。第二行是最大值扳碍。
樣例輸入：
8 3
1 3 -1 -3 5 3 6 7
樣例輸出：
-1 -3 -3 -3 3 3
3 3 5 5 6 7
涉及到和第一題類似的數(shù)據(jù)結(jié)構(gòu)提岔，單調(diào)隊列。但和單調(diào)棧不同的是單調(diào)隊列是雙向的笋敞。
找局部的最大值和最小值碱蒙，
1.首先維護雙端隊列的單調(diào)性，（假設(shè)從隊頭到隊尾遞減）當前元素若比隊尾元素值小夯巷，則彈出元素直到滿足條件赛惩。
2.同時要維護窗口內(nèi)的元素個數(shù)，如果隊首的元素已經(jīng)在窗口外趁餐，就把他彈出喷兼。
3.每一次循環(huán)的隊首元素就是當前窗口的最大值或者是最小值。
（同樣不太好理解QAQ）
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<deque>
#define MAXN 1000010
int a[MAXN];
int maxx[MAXN],minn[MAXN];
using namespace std;
int n,k;
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
deque<int> q;//儲存下標
for(int i=1;i<=k-1;i++)
{ while(!q.empty()&&a[q.back()]>a[i])
q.pop_back();
q.push_back(i);
}
for(int i=k;i<=n;i++)//窗口從k開始向右移動 維護一個單增隊列
{
while(!q.empty()&&a[q.back()]>a[i]) q.pop_back();//先維護單調(diào)性
q.push_back(i);
while(!q.empty()&&(i-q.front())>=k) q.pop_front();//然后維護窗口的大小
minn[i]=q.front();
}
q.clear();
for(int i=1;i<=k-1;i++)
{ while(!q.empty()&&a[q.back()]<a[i])
q.pop_back();
q.push_back(i);
}
for(int i=k;i<=n;i++)//窗口從k開始向右移動 維護一個單增隊列
{
while(!q.empty()&&a[q.back()]<a[i]) q.pop_back();//先維護單調(diào)性
q.push_back(i);
while(!q.empty()&&(i-q.front())>=k) q.pop_front();//然后維護窗口的大小
maxx[i]=q.front();
}
for(int i=k;i<=n;i++) printf("%d ",a[minn[i]]);
cout<<endl;
for(int i=k;i<=n;i++) printf("%d ",a[maxx[i]]);
cout<<endl;
system("pause");
return 0;
}
