题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1628
题意：
题解：
单调栈。
单调性：
栈内元素高度递增。
一旦出现比栈顶小的元素，则表明一栋房子的结束。
入栈：
如果出现了一个新的高度b（栈中没有），则入栈。
表明从现在开始，一定有一栋高度为b的房子，只是我们不知道它在哪里结束而已。
出栈：
对于现在的高度b，将栈中所有高度 > b的元素都出栈。
因为此时比b高的房子不得不结束。
每出栈一个元素，ans++。
注：最后要再多算一次b = 0，确保将最后一栋房子出栈。
AC Code:
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <stack> 5 6 using namespace std; 7 8 int n,w; 9 int ans=0; 10 stack<int> stk; 11 12 int main() 13 { 14 cin>>n>>w; 15 int a,b; 16 for(int i=0;i<=n;i++) 17 { 18 if(i<n) cin>>a>>b; 19 else b=0; 20 while(!stk.empty() && stk.top()>b) 21 { 22 stk.pop(); 23 ans++; 24 } 25 if(stk.empty() || stk.top()!=b) stk.push(b); 26 } 27 cout<<ans<<endl; 28 }
BZOJ 1628 [Usaco2007 Demo]City skyline：单调栈
原文：http://www.cnblogs.com/Leohh/p/7613318.html