最大矩形 —— 单调栈「建议收藏」

最大矩形 —— 单调栈「建议收藏」https://cn.vjudge.net/contest/245662#problemAhistogramisapolygoncomposedofasequenceofrectanglesalignedatacommonbaseline.Therectangleshaveequalwidthsbutmayhavedifferentheigh…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

https://cn.vjudge.net/contest/245662#problem

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 n integers h1,…,hn, where 0<=hi<=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

Hint

Huge input, scanf is recommended.

题意:

给定从左到右多个矩形,已知这此矩形的宽度都为1,长度不完全相等。这些矩形相连排成一排,求在这些矩形包括的范围内能得到的面积最大的矩形,打印出该面积。所求矩形可以横跨多个矩形,但不能超出原有矩形所确定的范围。

思路:

       易证, 最终求得的最大矩形的高度一定是某个小矩形的高度。因此对于每一个高度求出它左右用这个高度可以覆盖到的左右两个位置,用单调栈来计算L[i]和R[i],相乘后输出最大值即可。

       对于每一个小矩形,它能覆盖到的最左面的位置是L[i],那么L[i]-1位置上的矩形高度一定不会高于或等于H[i](否则就一定可以向左扩展),最右面的位置是R[i],那么R[i]+1位置上的矩形高度一定不会高于H[i]。

       我们可以分开维护L[i]和R[i],首先对于L[i],如果栈为空则直接将H[i]入栈,L[i]为0(说明前面没有比H[i]更小的高度)。若栈非空且栈顶元素大于当前的高度H[i],则弹出栈顶元素(原因见上一段,而且当前弹出的元素对后面入栈的元素一定没有影响,因为栈顶元素比弹出的元素高度更小且更靠近后面入栈的元素),直到栈顶元素小于H[i]为止,然后将H[i]入栈。维护R[i]的时候同理(左右没有区别)。

代码如下:

#include <iostream>
#include <cstdio>
using namespace std;

int st[100005], L[100005], R[100005], h[100005];

int main()
{
	int n;
	while (scanf("%d", &n)!=EOF){
		if (!n) break;
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &h[i]);
		}

		int l=0; 
		for (int i = 1; i <= n ; i++)
		{
			while (l>0 && h[st[l]] >= h[i]) l--;
			if (l==0) L[i] = 0;
			else L[i] = st[l];
			l++;
			st[l] = i;
		}

		l=0;
		for (int i=n; i>=0; i--){
			R[i] = i+1;
			while (l>0 && h[st[l]] >= h[i])	l--;
			if (l==0) R[i] = n+1;  
			else R[i] = st[l];
			l++;
			st[l] = i;
		}

		long long ans=0;
		for (int i=1; i<=n; i++)
		{
			if (ans < (long long)h[i]*(R[i] - L[i] - 1))
				ans = (long long)h[i]*(R[i] - L[i] - 1);
		}

		printf("%lld\n", ans);
	}
	
	return 0;
}

 

 

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/190688.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • nginx与tomcat配合部署web工程接口访问报414 Request-URI Too Large错误

    nginx与tomcat配合部署web工程接口访问报414 Request-URI Too Large错误首先查看nginx配置nginx.conf调节http模块以下参数值client_header_buffer_size512k;large_client_header_buffers4512k;如接口正常访问项目即修改有效;若报出"(104: Connection reset by peer) while connecting to upstream"继续检查tomcat下…

  • spdlog使用

    spdlog使用目录Spdlog优点Example简单封装与使用使用中遇到的问题Spdlog优点只需包含头文件 无需依赖第三方库 支持跨平台 支持多线程 源码地址:https://github.com/gabime/spdlog Example////Copyright(c)2015GabiMelman.//DistributedundertheMITLicense(http://opensource.org/licenses/MIT)/.

  • 字符串常量池理解「建议收藏」

    字符串常量池理解「建议收藏」在JVM中,为了减少字符串对象的重复创建,维护了一块特殊的内存空间,这块内存就被称为字符串常量池。在JDK1.6及之前,字符串常量池存放在方法区中。到JDK1.7之后,就从方法区中移除了,而存放在堆中。以下是《深入理解Java虚拟机》第二版原文:对于HotSpot虚拟机,根据官方发布的路线图信息,现在也有放弃永久代并逐步改为采用NativeMemory来实现方法区的规划了,在目前已经发布的…

  • perl正则表达式中文问题

    perl正则表达式中文问题
     
    在使用perl从地址中提取街道的时候遇到了个很诡异的问题
    同样一个地址,连续进行两次匹配出来的结果居然不一样
    一次是正常的,一次是乱码,搞了半天没弄明白是怎么回事
    看来perl的中文处理能力还是有待加强
    后来在进行正则匹配之前尝试用了useencoding”gbk”; 
    还算运气不错,居然搞定了
    useencoding”gbk”; 
    $address=~/^(.*(市|区))?(.*?(街|路|道)).*

  • 如何使用gitlab自带的CICD

    如何使用gitlab自带的CICD上次分享了gitlab+jenkins实现CICD,前提我们需要安装一个jenkins。其实高版本的gitlab已经具备CICD功能,笔者使用的版本是:GitLab社区版11.4.10安装RunnersSettings>CI/CD>Runners根据提示点击InstallGitlabRunner下面根据你的系统选择相应的安装包,笔者以linux为例:这里…

  • 快捷方式图标显示不正常_win10快捷方式不显示图标

    快捷方式图标显示不正常_win10快捷方式不显示图标win10系统的电脑近期遇到一个问题,那就是桌面上或者某磁盘中文件夹的程序快捷方式图标丢失显示异常,部分程序为一个白纸图标,不显示原本的程序图标,但是这些软件或者游戏的快捷方式能正常打开。那么游戏、软件等应用程序快捷方式不显示图标怎么办?下面装机之家分享一下Win10快捷方式图标变白纸解决方法。原因分析:在Win10系统中,首次对图标进行显示,为了加速图标的显示,之后系统会对图标进行缓存,如果缓存…

    2022年10月18日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号