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(单调栈）

推荐阅读

jsp
LeetCode 有效回文串 II：深入解析与优化算法

在 LeetCode 的“有效回文串 II”问题中，给定一个非空字符串 `s`，允许删除最多一个字符。本篇深入解析了如何判断删除一个字符后，字符串是否能成为回文串，并提出了高效的优化算法。通过详细的分析和代码实现，本文提供了多种解决方案，帮助读者更好地理解和应用这一算法。 ... [详细]

蜡笔小新 2024-11-11 17:40:42
jsp
系统数据实体验证异常：多个实体验证失败的错误处理与分析

在使用MVC和EF框架进行数据保存时，遇到了 `System.Data.Entity.Validation.DbEntityValidationException` 错误，表明存在一个或多个实体验证失败的情况。本文详细分析了该错误的成因，并提出了有效的处理方法，包括检查实体属性的约束条件、调试日志的使用以及优化数据验证逻辑，以确保数据的一致性和完整性。 ... [详细]

蜡笔小新 2024-11-11 16:54:45
jsp
装饰者模式（Decorator）：一种灵活的对象结构设计模式

装饰者模式（Decorator）是一种灵活的对象结构设计模式，旨在为单个对象动态地添加功能，而无需修改原有类的结构。通过封装对象并提供额外的行为，装饰者模式比传统的继承方式更加灵活和可扩展。例如，可以在运行时为特定对象添加边框或滚动条等特性，而不会影响其他对象。这种模式特别适用于需要在不同情况下动态组合功能的场景。 ... [详细]

蜡笔小新 2024-11-11 16:36:53
jsp
【Python 实战：汇率转换器 v1.02】

本项目通过Python编程实现了一个简单的汇率转换器v1.02。主要内容包括：1. Python的基本语法元素：（1）缩进：用于表示代码的层次结构，是Python中定义程序框架的唯一方式；（2）注释：提供开发者说明信息，不参与实际运行，通常每个代码块添加一个注释；（3）常量和变量：用于存储和操作数据，是程序执行过程中的重要组成部分。此外，项目还涉及了函数定义、用户输入处理和异常捕获等高级特性，以确保程序的健壮性和易用性。 ... [详细]

蜡笔小新 2024-11-11 16:34:26
jsp
Autofac高级应用实例解析

本文详细解析了Autofac在高级应用场景中的具体实现，特别是如何通过注册泛型接口的类来优化依赖注入。示例代码展示了如何使用 `builder.RegisterAssemblyTypes` 方法，结合 `typeof(IEventHandler).Assembly` 和 `Where` 过滤条件，动态注册所有符合条件的类，从而简化配置并提高代码的可维护性。此外，文章还探讨了这一方法在复杂系统中的实际应用及其优势。 ... [详细]

蜡笔小新 2024-11-11 15:48:02
jsp
华为云对象存储系统配置指南

本指南详细介绍了如何利用华为云对象存储服务构建视频点播（VoD）平台。通过结合开源技术如Ceph、WordPress、PHP和Nginx，用户可以高效地实现数据存储、内容管理和网站搭建。主要内容涵盖华为云对象存储系统的配置步骤、性能优化及安全设置，为开发者提供全面的技术支持。 ... [详细]

蜡笔小新 2024-11-11 14:29:52
jsp
VS2019 在创建 Windows 恢复点时出现卡顿问题及解决方法

在使用 Visual Studio 2019 时，有时会在创建 Windows 恢复点时遇到卡顿问题。这可能是由于频繁的自动更新导致的，每次更新文件大小可能达到 1-2GB。尽管现代网络速度较快，但这些更新仍可能对系统性能产生影响。本文将探讨该问题的原因，并提供有效的解决方法，帮助用户提升开发效率。 ... [详细]

蜡笔小新 2024-11-11 13:52:39
jsp
Keepalived VIP 漂移故障分析与解决

在分析和解决 Keepalived VIP 漂移故障的过程中，我们发现主备节点配置如下：主节点 IP 为 172.16.30.31，备份节点 IP 为 172.16.30.32，虚拟 IP 为 172.16.30.10。故障表现为监控系统显示 Keepalived 主节点状态异常，导致 VIP 漂移到备份节点。通过详细检查配置文件和日志，我们发现主节点上的 Keepalived 进程未能正常运行，最终通过优化配置和重启服务解决了该问题。此外，我们还增加了健康检查机制，以提高系统的稳定性和可靠性。 ... [详细]

蜡笔小新 2024-11-11 09:31:14
jsp
Android 中的 exported 属性详解与应用

在 Android 开发中，`android:exported` 属性用于控制组件（如 Activity、Service、BroadcastReceiver 和 ContentProvider）是否可以被其他应用组件访问或与其交互。若将此属性设为 `true`，则允许外部应用调用或与之交互；反之，若设为 `false`，则仅限于同一应用内的组件进行访问。这一属性对于确保应用的安全性和隐私保护至关重要。 ... [详细]

蜡笔小新 2024-11-10 14:14:26
jsp
飞秋软件的OA消息接口服务系统

为了提升单位内部沟通效率，我们开发了一套飞秋软件与OA系统的消息接口服务系统。该系统能够将OA系统中的审批、通知等信息自动同步至飞秋平台，确保员工在使用飞秋进行日常沟通的同时，也能及时获取OA系统的各类重要信息，从而实现无缝对接，提高工作效率。 ... [详细]

蜡笔小新 2024-11-11 13:44:09
jsp
深入解析浏览器内核与版本的发展历程

浏览器作为我们日常不可或缺的软件工具，其背后的运作机制却鲜为人知。本文将深入探讨浏览器内核及其版本的演变历程，帮助读者更好地理解这一关键技术组件，揭示其内部运作的奥秘。 ... [详细]

蜡笔小新 2024-11-11 13:34:37
jsp
如何在 Vim 编辑器中调整和自定义配色方案

Vim 编辑器功能强大，但其默认的配色方案往往不尽如人意，尤其是注释颜色为蓝色时，对眼睛极为不友好。为了提升编程体验，自定义配色方案显得尤为重要。通过合理调整颜色，不仅可以减轻视觉疲劳，还能显著提高编码效率和兴趣。 ... [详细]

蜡笔小新 2024-11-11 12:34:19
jsp
虚函数表指针vptr的功能测试与分析

类的虚函数调用依赖于虚函数表来实现。虚函数表是由编译器自动生成的一段内存区域，用于存储包含虚函数的类中每个虚函数的入口地址。这些入口地址本质上是指针类型，从而使得动态绑定成为可能。本文对虚函数表指针（vptr）的功能进行了详细的测试与分析，探讨了其在多态性和继承机制中的作用及其性能影响。 ... [详细]

蜡笔小新 2024-11-11 10:41:37
jsp
如何在 Mac 上查看隐藏的文件和文件夹：专业指南

在 Mac 上查看隐藏文件和文件夹的详细指南。通过终端命令，您可以轻松地显示或隐藏这些文件。具体步骤如下：输入 `defaults write com.apple.finder AppleShowAllFiles -bool true` 以显示所有隐藏文件，或使用 `defaults write com.apple.finder AppleShowAllFiles -bool false` 以重新隐藏它们。此方法适用于各种版本的 macOS，帮助用户更好地管理和访问系统文件。 ... [详细]

蜡笔小新 2024-11-10 14:55:22
jsp
逻辑运算符“与”和“或”的使用解析

本文详细解析了逻辑运算符“与”（&&）和“或”（||）在编程中的应用。通过具体示例，如 `[dehua@teacher~]$[$(id -u) -eq 0] && echo "You are root" || echo "You must be root"`，展示了如何利用这些运算符进行条件判断和命令执行。此外，文章还探讨了这些运算符在不同编程语言中的实现和最佳实践，帮助读者更好地理解和运用逻辑运算符。 ... [详细]

蜡笔小新 2024-11-10 14:50:01

手机用户2502900545

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

Tags | 热门标签

RankList | 热门文章