Largest Rectangle in a Histogram POJ - 2559（直方图最大面积，单调栈）

本文主要是介绍Largest Rectangle in a Histogram POJ - 2559（直方图最大面积，单调栈），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

直方图中最大的矩形
题目
提交记录
讨论
题解
视频讲解

直方图是由在公共基线处对齐的一系列矩形组成的多边形。

矩形具有相等的宽度，但可以具有不同的高度。

例如，图例左侧显示了由高度为2,1,4,5,1,3,3的矩形组成的直方图，矩形的宽度都为1：

2559_1.jpg

通常，直方图用于表示离散分布，例如，文本中字符的频率。

现在，请你计算在公共基线处对齐的直方图中最大矩形的面积。

图例右图显示了所描绘直方图的最大对齐矩形。

输入格式
输入包含几个测试用例。

每个测试用例占据一行，用以描述一个直方图，并以整数n开始，表示组成直方图的矩形数目。

然后跟随n个整数h1，…，hn。

这些数字以从左到右的顺序表示直方图的各个矩形的高度。

每个矩形的宽度为1。

同行数字用空格隔开。

当输入用例为n=0时，结束输入，且该用例不用考虑。

输出格式
对于每一个测试用例，输出一个整数，代表指定直方图中最大矩形的区域面积。

每个数据占一行。

请注意，此矩形必须在公共基线处对齐。

数据范围
1≤n≤100000,
0≤hi≤1000000000
输入样例：
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
输出样例：
8
4000
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.

https://blog.csdn.net/tomjobs/article/details/99764440
这里解释了一下单调栈和单调队列的关系，这里单调栈就是求左右第一个比这个数小的数，本质和单调队列没有区别

NEW：话说这不就是单调队列只开一头，并且对于每一个节点多维护几个信息吗？？单调队列和单调栈不是一个东西吗？

ACNEW

#include <cstdio>
#include <algorithm>
#include <cstring>using namespace std;typedef long long ll;
const int maxn = 1e5 + 7;
struct STK
{int id,len;ll val;
}stk[maxn];ll a[maxn];
int main()
{int n;while(~scanf("%d",&n) && n){a[n + 1] = 0;int top = 0;ll ans = 0;for(int i = 1;i <= n + 1;i ++){if(i != n + 1)scanf("%lld",&a[i]);if(a[i] > stk[top].val){stk[++top].val = a[i];stk[top].id = i;stk[top].len = 1;}else{int len = 0;while(a[i] <= stk[top].val && top > 0){len += stk[top].len;ans = max(ans,len * stk[top].val);top--;}stk[++top].val = a[i];stk[top].id = i;stk[top].len = len + 1;}}printf("%lld\n",ans);}return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>using namespace std;typedef long long ll;
const int maxn = 1e5 + 7;
int a[maxn],s[maxn],w[maxn];int main()
{int n;while(~scanf("%d",&n) && n){int t = 0;a[n + 1] = 0;ll ans = 0;for(int i = 1;i <= n + 1;i++){if(i != n + 1)scanf("%d",&a[i]);if(a[s[t]] < a[i]){s[++t] = i;w[t] = 1;}else{int l = 0;while(a[s[t]] > a[i]){l += w[t];//l是右边积累来的范围，w[t]是左边积累的范围，加起来是总的比其高影响范围。ans = max(ans,(ll)l * a[s[t]]);t--;}s[++t] = i;w[t] = l + 1;}}printf("%lld\n",ans);}return 0;
}