單調棧3_水到極致的題 HDOJ4252

A Famous City

題目大意 給出正視圖? 每一列為樓的高度 最少有幾座樓

坑點 樓高度可以為0 代表沒有樓

貢獻了兩發RE 原因 if(!s.empty()&&tem){s.push(tem); continue;}并不能篩去 空棧且 tem為0的情況

改為 if(!s.empty()){if(tem) s.push(tem); continue;} 后AC

題目思路 維護一個單調遞增的棧? 假如新加入的樓高度小于top元素 那我們知道top元素一定是單獨的一棟樓 我們就pop掉 ans++

如果 等于top 那么可以認為 這兩個是一棟樓（最少）

如果大于pop? 就添加下一個

操作結束后 剩余在棧內的元素 每一個必然是獨立的一棟樓

樓的高度0 一定要特判

對棧進行top pop 這些操作前一定要判empty啊

代碼如下

#include<cstdio>
#include<map>
//#include<bits/stdc++.h>
#include<vector>
#include<stack>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<cstdlib>
#include<climits>
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef __int64 int64;
const ll mood=1e9+7;
const int64 Mod=998244353;
const double eps=1e-9;
const int N=2e7+10;
const int MAXN=1e5+5;
inline void rl(ll&num){num=0;ll f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();num*=f;
}
inline void ri(int &num){num=0;int f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();num*=f;
}
int getnum()//相鄰的個位整數輸入 如想分別保存1234 輸入連續的1234 a[i]=getnum();就可以實現
{char ch=getchar();while((ch<'0' || ch>'9') && ch!='-')ch=getchar();return (ch-'0');
}
inline void out(int x){ if(x<0) {putchar('-');  x*=-1;}if(x>9) out(x/10);    putchar(x%10+'0'); }
int main()
{int n,ci=0;while(scanf("%d",&n)!=EOF){int tem;ll ans=0;stack<int>s;for(int i=0;i<n;i++){ri(tem);if(s.empty()){if(tem)s.push(tem);continue;}if(s.top()==tem) continue;if(tem<s.top()){while(!s.empty()&&s.top()>tem){s.pop();ans++;}if(!s.empty()&&s.top()==tem) continue;else{if(tem)s.push(tem);}}else{if(tem)s.push(tem);}}printf("Case %d: ",++ci);ans+=s.size();cout<<ans<<endl;}return 0;
}

?