频道栏目
首页 > 程序开发 > 软件开发 > C语言 > 正文
51nod 1102 面积最大的矩形(单调栈)
2017-06-19 09:35:09      个评论    来源:泡海水的咸鱼  
收藏   我要投稿

51nod 1102 面积最大的矩形(单调栈)

以i所指的矩形高度作为要组成的矩形的高度,分别向左右扩展。用单调栈维护一个left数组和一个right数组,记录向左右能扩展到的边界,然后扫一遍出结果。

#include 
#include 
#include 
using namespace std;

const int MAXN = 5e4+10;
long long num[MAXN];
int lt[MAXN],rt[MAXN];

int main()
{
    int n;
    cin >> n;
    num[1] = 0;
    for(int i = 2; i <= n+1; ++i)
        cin >> num[i];
    num[n+2] = 0;
    n += 2;
    stack s1,s2;
    for(int i = 1; i <= n; ++i)
    {
        while(s1.size() && num[s1.top()] >= num[i])
            s1.pop();
        if(s1.size()) lt[i] = s1.top()+1;
        else lt[i] = i;
        s1.push(i);
    }
    for(int i = n; i >= 1; --i)
    {
        while(s2.size() && num[s2.top()] >= num[i])
            s2.pop();
        if(s2.size()) rt[i] = s2.top()-1;
        else rt[i] = i;
        s2.push(i);
    }
    long long res = 0;
    for(int i = 1; i <= n; ++i)
        res = max(res,(rt[i]-lt[i]+1)*num[i]);
    cout << res << endl;
    return 0;
}
点击复制链接 与好友分享!回本站首页
相关TAG标签 单调栈 矩形高度
上一篇:插入排序算法
下一篇:C语言中指针探秘
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站