当前位置: 代码迷 >> 综合 >> HDU1506-单调栈
  详细解决方案

HDU1506-单调栈

热度:16   发布时间:2024-01-18 01:07:04.0

题意:求连续区间内矩形覆盖的最大面积,连续区间内矩形宽度都为1 , 高度只能取最小高度

题解:维护一个单调递减的单调栈

对于一个新的元素:
(1)如果此时栈为空或者栈顶元素比新元素小,则将该元素入栈;
(2)如果栈顶元素与新元素相等,则跳过新元素;
(3)如果栈顶元素比新元素大,那么此时需要更新栈顶元素并更新面积,一直到栈顶元素小于新元素为止。

#include<iostream>
#include<stdio.h>
#include<stack>
using namespace std;__int64 hight[100010], ans,sum;int main()
{int n,i,temp;while(scanf("%d",&n),n){for(i=0; i<n; ++i)scanf("%I64d",&hight[i]);ans = -2147483647;hight[n]=-1;stack<int>q;for(i=0; i<=n; ++i){if(q.empty() || hight[i]>hight[q.top()]){q.push(i);}else if(hight[i]<hight[q.top()]){while(!q.empty() && hight[q.top()]>hight[i]){sum = (i-q.top())*hight[q.top()];if(sum>ans)ans = sum;temp = q.top();  //记录出栈的元素的下标。q.pop();}q.push(temp);  //此时temp下标表示以hight[i]为高度的矩形的左边的边界(因为栈是递减的,所以左边的比右边的高)hight[temp] = hight[i];  //这里注意理解,把hight[i]的值赋值给hight[temp](原来的高度已经没用了),此时它表示的是高为hight[i]的矩形}}printf("%I64d\n",ans);}return 0;
}


  相关解决方案