# [题解] 单调栈与单调队列练习题

## 例题

### 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


### 解题思路

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>

using namespace std;

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(){

for(register int i=0; i<n; i++){

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 住他们

### Sample Input

5
1 2
1 3
2 2
2 5
1 4


### Sample Output

4


### 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>

using namespace std;

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(){

for(register int i=1; i<=n; i++){

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;

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[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;

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(){

for(register int i=1; i<=k; i++){
push(x, i);
}

for(register int i=k+1; i<=n; i++){
pop(i-k);
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;
}