# 描述

http://www.lydsy.com/JudgeOnline/problem.php?id=1628

# 分析

``` 1 #include <bits/stdc++.h>
2 using namespace std;
3
4 const int maxn=50000+5;
5 int n,m,top,ans;
6 int a[maxn],s[maxn];
7 int main(){
8     scanf("%d%d",&n,&m); ans=n;
9     for(int i=1;i<=n;i++) scanf("%d",&a[i]), scanf("%d",&a[i]);
10     for(int i=1;i<=n;i++){
11         while(s[top]>a[i]) top--;
12         if(s[top]==a[i]) ans--;
13         else s[++top]=a[i];
14     }
15     printf("%d\n",ans);
16     return 0;
17 }```

## 1628: [Usaco2007 Demo]City skyline

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 432  Solved: 344
[Submit][Status][Discuss]

## Sample Input

10 26
1 1
2 2
5 1
6 3
8 1
11 0
15 2
17 3
20 2
22 1

INPUT DETAILS:

The case mentioned above

6

Silver

## （单调栈）poj-2559 Largest Rectangle in a Histogram

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

## POJ 3415 Common Substrings（后缀数组+单调栈）

[题目链接] http://poj.org/problem?id=3415 [题目大意] 求出两个字符串长度大于k的公共子串的数目. [题解] 首先,很容易想到O(n2)的算法,将A串和B串加拼接符相连, 做一遍后缀数组,把分别属于A和B的所有后缀匹配,LCP-k+1就是对答案的贡献, 但是在这个基础上该如何优化呢. 我们可以发现按照sa的顺序下来,每个后缀和前面的串的LCP就是区间LCP的最小值, 那么我们维护一个单调栈,将所有单调递减的LCP值合并, 保存数量和长度,对每个属于B串的后缀更新

## poj2796 维护区间栈//单调栈

http://poj.org/problem?id=2796 题意:给你一段区间,需要你求出(在这段区间之类的最小值*这段区间所有元素之和)的最大值...... 例如: 6 3 1 6 4 5 2 以4为最小值,向左右延伸,6 4 5  值为60....... 思路:解决完为这道题目,我才真正明白了单调栈的原理,它就是以某一个值为最小(最大)值,向这个值的两侧延伸,遇到大于它(小于它)的值,就将它延伸的范围扩大,当然,一般来说,要这样做的算法复杂度为o(n^2),但是借助栈这个玩意,维护其单调增

## hdu 5875(单调栈)

Function Time Limit: 7000/3500 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 1866    Accepted Submission(s): 674 Problem Description The shorter, the simpler. With this problem, you should be convinced of this tr