Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
有N个矩形，矩形的底边边长为1，且均在X轴上，高度给出，第i个矩形的高为h[i]，例如h = [3, 2, 4, 2]的图形如下：
你可以容易地发现，只需要3个矩形就能覆盖这个图形。 你的任务就是，输出最少需要几个矩形能覆盖这个图形。 【输入格式】
第一行一个整数N。接下来1行包含N个正整数，为h[i]。【输出格式】
输出一个整数表示最少需要几个矩形能覆盖这个图形。
【数据规模】
对于所有数据，N<=100000，h[i] <= 100。 对于部分数据，N<=10； 对于部分数据，N<=100； 对于部分数据，N<=1000； 对于部分数据，h[i] <= 10；
Sample Input1
10 2 3 2 4 2 1 3 4 3 2【题解】
像是题目给的那张图
会发现前3列。3 2 4无论如何都没有办法用少于3个矩形覆盖。
而第4列2确可以省掉一个。
因为我们可以横着用一条长的把第2列和第3列都覆盖到
假想一下旁边还有一个高度为2的。也同样可以覆盖掉。
但如果是这样却不能省
虽然1和4高度都为2.
但是你中间有比这两个2低的1.
这下你可没办法弄一个长长的矩形同时覆盖它们俩了。
事实上如果后面出现2或者3都没有可能节省了，因为1比2和3都矮，都和这种情况相似(即虽然前面有一样高度的但是没办法省一个矩形)。
由此。我们可以用栈来解决这个问题。
如果栈为空就把当前这个高度入栈。
否则。如果当前元素比栈顶元素高。则入栈。
否则一直退栈。直到满足当前元素比栈顶元素高或恰好等于栈顶元素。
如果恰好等于则不要入栈(表示省了一个矩形)。
最后统计入过栈的元素的个数。就是答案了。
【代码】
#include <cstdio>
int n,stack[100009] = {0},top = 0,num = 0;
void input_data()
{
scanf("%d",&n);
for (int i = 1;i <= n;i++)
{
int x;
scanf("%d",&x);
while (stack[top] > x) //如果比栈顶元素矮则一直退栈
top--;
if (stack[top]!=x) //如果和栈顶元素不一样(就是大于了)
{
stack[++top] = x; //入栈
num++; //答案递增。
}
}
}
void output_ans()
{
printf("%d",num); //最后输出入过栈的元素个数。
}
int main()
{
input_data();
output_ans();
return 0;
}