矩形覆盖

我又回来了，终于回来了！

上一次写还是八月份，最近有点忙，开学终于有时间了，先发道短的。

题目描述：
有N个矩形，矩形的底边边长为1，且均在X轴上，高度给出，第i个矩形的高为h[i]，例如h = [3, 2, 4, 2]的图形如下：
你可以容易地发现，只需要3个矩形就能覆盖这个图形。
你的任务就是，输出最少需要几个矩形能覆盖这个图形。
输入格式:
第一行一个整数N。接下来1行包含N个正整数，为h[i]。
输出格式:
输出一个整数表示最少需要几个矩形能覆盖这个图形。
样例输入：
10
2 3 2 4 2 1 3 4 3 2
样例输出：
7
数据规模：
对于所有数据，N<=100000，h[i] <= 100。
对于部分数据，N<=10；
对于部分数据，N<=100；
对于部分数据，N<=1000；
对于部分数据，h[i] <= 10；

这题的思路是用单调队列，维护一个单调递增的队列，读入一个数，放入队列中，
维护队列的单调性。如果最后x>top，答案就+1，x==top，就直接continue。

#include<bits/stdc++.h>
#define zz -1
using namespace std;
int i,j,k,n,m,tot,ans,top,re;
int f[100005];
int read(){
    char c;int x;while(c=getchar(),c<'0'||c>'9');x=c-'0';
    while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';
    return x;
}
int main()
{
    n=read();top=0;f[0]=zz;
    for(int i=1;i<=n;i++){
        int x=read();
        while(x<f[top]){
            top--;
        }
        if(x==f[top]) continue;
        if(x>f[top]){
            ans++;
            f[++top]=x;
        }
    }
    printf("%d",ans);
    return 0;
}