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

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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;
}