单调队列：从队首到队尾元素 单调递增 或者 单调递减 的队列
单调栈：从栈顶到栈底元素 单调递增 或者 单调递减 的栈
Contents
常见用法
单调栈：给出一个数组，对于一个下标为 $i$ 的数 $x$，询问其 左/右 边第一个比 $x$ 大/小 的数
单调队列：给出一个数组，对于每一个长度为 $k$ 的连续子序列，求出子序列中的最大值或最小值
例题
POJ – 3250 Bad Hair Day
Descrition
Some of Farmer John’s $N$ cows (1 ≤ $N$ ≤ 80,000) are having a bad hair day! Since each cow is self-conscious about her messy hairstyle, FJ wants to count the number of other cows that can see the top of other cows’ heads.
Each cow i has a specified height $h_i$ (1 ≤ $h_i$ ≤ 1,000,000,000) and is standing in a line of cows all facing east (to the right in our diagrams). Therefore, cow $i$ can see the tops of the heads of cows in front of her (namely cows $i+1$, $i+2$, and so on), for as long as these cows are strictly shorter than cow $i$.
Consider this example:
* * * * = *
= * * * = *
= * - * = * Cows facing right -->
= * = * = *
= - = = = *
= = = = = =
Cow#1 can see the hairstyle of cows #2, 3, 4
Cow#2 can see no cow’s hairstyle
Cow#3 can see the hairstyle of cow #4
Cow#4 can see no cow’s hairstyle
Cow#5 can see the hairstyle of cow 6
Cow#6 can see no cows at all!
Let $c_i$ denote the number of cows whose hairstyle is visible from cow i; please compute the sum of $c_1$ through $c_n$ .For this example, the desired is answer $3 + 0 + 1 + 0 + 1 + 0 = 5$.
Input
Line 1: The number of cows, N.
Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i.
Output
Line 1: A single integer that is the sum of $c_1$ through $c_N$.
Sample Input
6
10
3
7
4
12
2
Sample Output
5
解题思路
维护一个单调递增栈，从左到右枚举，若栈内元素有 $x$ 个，每一头牛都可以都可以被 $x$ 头牛看见，统计答案即可
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
using namespace std;
inline int read(){
int x = 0;
char ch = getchar();
while(ch < '0' || ch > '9')
ch = getchar();
while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}
return x;
}
int n;
long long ans;
stack <int> sta;
int main(){
n = read();
for(register int i=0; i<n; i++){
int x = read();
while(!sta.empty() && x >= sta.top()){
sta.pop();
}
ans += sta.size();
sta.push(x);
}
printf("%lld", ans);
return 0;
}
BZOJ-1103 海报PLA
Description
$N$ 个矩形，排成一排，现在希望用尽量少的矩形海报 Cover 住他们
Input
第一行给出数字 $N$，代表有 $N$ 个矩形。$N$ 在 $[1, 250000]$ 下面 $N$ 行，每行给出矩形的长与宽。其值在 $[1, 100000000]$
Output
最少的数量的海报数
Sample Input
5
1 2
1 3
2 2
2 5
1 4
Sample Output
4
解题思路
最多需要 $n$ 张海报，记录有多少张海报可以被抵消即可。维护一个单调递减栈，如果当前海报高度与栈顶元素相同，说明可以被抵消。（当出现一个凹字形结构时之前更高的海报会全部从栈中清除）
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
using namespace std;
inline int read(){
int x = 0;
char ch = getchar();
while(ch < '0' || ch > '9')
ch = getchar();
while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}
return x;
}
int n;
int ans;
stack <int> sta;
int main(){
ans = n = read();
for(register int i=1; i<=n; i++){
int x = read();
int y = read();
while(!sta.empty() && y < sta.top())
sta.pop();
if(!sta.empty() && y == sta.top())
ans--;
sta.push(y);
}
printf("%d", ans);
return 0;
}
HDU – 1506 Largest Rectangle in a Histogram
Description
A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:
Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.
Input
The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1 <= n <= 100000. Then follow n integers h1, …, hn, where 0 <= hi <= 1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.
Output
For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.
Sample Input
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
Sample Output
8
4000
解题思路
对于每一个矩形，我们枚举用它的高度作为最小值的区间最长能到达哪里，用两个数组表示，最后枚举统计答案
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
using namespace std;
const int MAXN = 100000 + 10;
inline int read(){
int x = 0;
char ch = getchar();
while(ch < '0' || ch > '9')
ch = getchar();
while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}
return x;
}
stack <int> sta;
int l[MAXN], r[MAXN], h[MAXN];
int n;
int main(){
while(scanf("%d", &n) == 1 && n){
for(register int i=1; i<=n; i++)
h[i] = read();
h[0] = h[n+1] = -1;
for(register int i=1; i<=n+1; i++){
while(!sta.empty() && h[i] < h[sta.top()]){
r[sta.top()] = i-1;
sta.pop();
}
sta.push(i);
}
for(register int i=n; i>=0; i--){
while(!sta.empty() && h[i] < h[sta.top()]){
l[sta.top()] = i+1;
sta.pop();
}
sta.push(i);
}
long long ans = 0;
for(register int i=1; i<=n; i++){
ans = max(ans, h[i] * (r[i] - l[i] + 1LL));
}
printf("%lld\n", ans);
}
return 0;
}
POJ – 2823 Sliding Window
Description
An array of size $n \leq 10^6$ is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:
The array is [1 3 -1 -3 5 3 6 7], and k is 3.
Your task is to determine the maximum and minimum values in the sliding window at each position.
Input
The input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line.
Output
There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.
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
解题思路
单调队列的应用，使用双端队列来实现。每一个新元素在队尾入队，由于元素入队导致不符单调性的元素在队尾出队，其他正常出队操作带队首出队
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN = 1000000 + 10;
inline int read(){
int x = 0;
int p = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-')
p = 0;
ch = getchar();
}
while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}
return p ? x : (-x);
}
struct Data{
int num;
int id;
};
bool operator <= (Data a, Data b){
return a.num <= b.num;
}
bool operator >= (Data a, Data b){
return a.num >= b.num;
}
deque <Data> que_1, que_2;
int n, k;
int cnt, ans_1[MAXN], ans_2[MAXN];
inline void push(int x, int id){
while(!que_1.empty() && x >= que_1.back().num){
que_1.pop_back();
}
que_1.push_back((Data){x, id});
while(!que_2.empty() && x <= que_2.back().num){
que_2.pop_back();
}
que_2.push_back((Data){x, id});
}
inline void pop(int time){
while(que_1.front().id < time){
que_1.pop_front();
}
while(que_2.front().id < time){
que_2.pop_front();
}
ans_1[++cnt] = que_1.front().num;
ans_2[cnt] = que_2.front().num;
}
int main(){
n = read();
k = read();
for(register int i=1; i<=k; i++){
int x = read();
push(x, i);
}
for(register int i=k+1; i<=n; i++){
pop(i-k);
int x = read();
push(x, i);
}
pop(n-k+1);
for(register int i=1; i<=cnt; i++){
printf("%d ", ans_2[i]);
}
printf("\n");
for(register int i=1; i<=cnt; i++){
printf("%d ", ans_1[i]);
}
return 0;
}