POJ2559LargestRectangleinaHistogram(单调栈）

作者：手机用户2502900545 | 来源：互联网 | 2023-09-15 20:22

DescriptionAhistogramisapolygoncomposedofasequenceofrectanglesalignedatacommonbaseli

Description

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:
技术分享

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

Input

The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1<=n<=100000. Then follow nintegers h₁,...,h_n, where 0<=h_i<=1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.

Output

For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.

Sample Input

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

Sample Output

8
4000

学习了下单调栈写法。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i pil;
const int INF = 0x3f3f3f3f;
const int maxn=1e5+100;
struct node{
    int val;
    int pos;
};
stacks;
int n,a[maxn];
int main()
{
    node st;
    while(~scanf("%d",&n)&&n)
    {
        REPF(i,1,n)
          scanf("%d",&a[i]);
        st.val=st.pos=0;
        s.push(st);LL ans=0;
        for(int i=1;i<=n;i++)
        {
            st.pos=i;
            while(s.top().val>a[i])
            {
                st=s.top();
                s.pop();
                LL temp=(LL)st.val*(i-st.pos);
                ans=max(ans,temp);
            }
            st.val=a[i];
            s.push(st);
        }
        while(!s.empty())
        {
            st=s.top();
            LL temp=(LL)st.val*(n-st.pos+1);
            ans=max(ans,temp);
            s.pop();
        }
        printf("%I64d\n",ans);
    }
    return 0;
}


/*

*/

以前习惯这样写。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i pil;
const int INF = 0x3f3f3f3f;
const int maxn=1e5+100;
int l[maxn],r[maxn];
int n,num[maxn];
int main()
{
    while(~scanf("%d",&n)&&n)
    {
        REPF(i,1,n)
            scanf("%d",&num[i]);
        l[1]=1;
        REPF(i,2,n)
        {
            int pos=i;
            while(pos-1>=1&&num[i]<=num[pos-1])
                pos=l[pos-1];
            l[i]=pos;
        }
        r[n]=n;
        for(int i=n-1;i>=1;i--)
        {
            int pos=i;
            while(pos+1<=n&&num[i]<=num[pos+1])
                pos=r[pos+1];
            r[i]=pos;
        }
        LL ans=0;
        REPF(i,1,n)
            ans=max(ans,(LL)num[i]*(r[i]-l[i]+1));
        printf("%lld\n",ans);
    }
    return 0;
}

POJ 2559 Largest Rectangle in a Histogram(单调栈）

推荐阅读

int
Python学习笔记：使用pydoc工具查询文档

本文介绍了在Windows环境下使用pydoc工具的方法，并详细解释了如何通过命令行和浏览器查看Python内置函数的文档。此外，还提供了关于raw_input和open函数的具体用法和功能说明。 ... [详细]

蜡笔小新 2024-12-26 17:05:56
int
Linux 自动化安装脚本详解

本文介绍了一款用于自动化部署 Linux 服务的 Bash 脚本。该脚本不仅涵盖了基本的文件复制和目录创建，还处理了系统服务的配置和启动，确保在多种 Linux 发行版上都能顺利运行。 ... [详细]

蜡笔小新 2024-12-27 16:33:32
int
QUIC协议：快速UDP互联网连接

QUIC（Quick UDP Internet Connections）是谷歌开发的一种旨在提高网络性能和安全性的传输层协议。它基于UDP，并结合了TLS级别的安全性，提供了更高效、更可靠的互联网通信方式。 ... [详细]

蜡笔小新 2024-12-28 12:33:18
php
深入理解OAuth认证机制

本文介绍了OAuth认证协议的核心概念及其工作原理。OAuth是一种开放标准，旨在为第三方应用提供安全的用户资源访问授权，同时确保用户的账户信息（如用户名和密码）不会暴露给第三方。 ... [详细]

蜡笔小新 2024-12-28 12:07:46
int
编写有趣的VBScript恶作剧脚本

本文将介绍如何编写一些有趣的VBScript脚本，这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例，帮助您了解VBScript的基本语法和功能。 ... [详细]

蜡笔小新 2024-12-28 09:46:23
int
Python配置文件读写指南

本文详细介绍如何使用Python进行配置文件的读写操作，涵盖常见的配置文件格式（如INI、JSON、TOML和YAML），并提供具体的代码示例。 ... [详细]

蜡笔小新 2024-12-28 08:39:55
php
CSS 布局：液态三栏混合宽度布局

本文介绍了如何使用 CSS 实现液态的三栏布局，其中各栏具有不同的宽度设置。通过调整容器和内容区域的属性，可以实现灵活且响应式的网页设计。 ... [详细]

蜡笔小新 2024-12-28 02:40:28
php
在Linux系统中配置并启动ActiveMQ

本文详细介绍了如何在Linux环境中安装和配置ActiveMQ，包括端口开放及防火墙设置。通过本文，您可以掌握完整的ActiveMQ部署流程，确保其在网络环境中正常运行。 ... [详细]

蜡笔小新 2024-12-27 14:38:54
schema
MySQL中枚举类型的所有可能值获取方法

本文介绍了一种在MySQL数据库中查询枚举（ENUM）类型字段所有可能取值的方法，帮助开发者更好地理解和利用这一数据类型。 ... [详细]

蜡笔小新 2024-12-27 10:36:44
int
使用 NSTimer 实现倒计时功能

本文介绍如何使用 NSTimer 实现倒计时功能，详细讲解了初始化方法、参数配置以及具体实现步骤。通过示例代码展示如何创建和管理定时器，确保在指定时间间隔内执行特定任务。 ... [详细]

蜡笔小新 2024-12-26 19:08:19
int
深入理解 Oracle 存储函数：计算员工年收入

本文介绍如何使用 Oracle 存储函数查询特定员工的年收入。我们将详细解释存储函数的创建过程，并提供完整的代码示例。 ... [详细]

蜡笔小新 2024-12-28 09:49:42
php
四载相伴，与51CTO学院共成长

在计算机技术的学习道路上，51CTO学院以其专业性和专注度给我留下了深刻印象。从2012年接触计算机到2014年开始系统学习网络技术和安全领域，51CTO学院始终是我信赖的学习平台。 ... [详细]

蜡笔小新 2024-12-28 08:20:07
php
Xcode 中多行代码缩进技巧

本文介绍如何在 Xcode 中使用快捷键和菜单命令对多行代码进行缩进，包括右缩进和左缩进的具体操作方法。 ... [详细]

蜡笔小新 2024-12-27 17:52:34
int
分页插件3指定到某一页

前言--页数多了以后需要指定到某一页（只做了功能，样式没有细调）html ... [详细]

蜡笔小新 2024-12-27 15:19:01
php
实现密码输入框的掩码设置

本文介绍如何在应用程序中使用文本输入框创建密码输入框，并通过设置掩码来隐藏用户输入的内容。我们将详细解释代码实现，并提供专业的补充说明。 ... [详细]

蜡笔小新 2024-12-27 02:22:09

手机用户2502900545

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章