Acwing - 131. 直方图中最大的矩形

131. 直方图中最大的矩形 - AcWing题库

题目描述

tag : 单调栈

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

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

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

输入格式

输入包含几个测试用例。

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

然后跟随 n 个整数 h 1 ， … ， h n h_1，…，h_n h1​，…，hn​。

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

每个矩形的宽度为 1。

同行数字用空格隔开。

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

输出格式

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

每个数据占一行。

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

数据范围

1≤n≤100000
0 ≤ h i ≤ 1000000000 0≤h_i≤1000000000 0≤hi​≤1000000000

样例

输入样例：

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

输出样例：

8
4000

题目的意思是让我们求出最大的矩形面积。

我们一开始可以先想一想最简单的方法应该怎么求。一个矩形的面积有两个属性，宽和高。高我们可以通过读入的数据一次获取，但是矩形的宽度就需要我们去枚举了。

也就是说，对于 i 位置的矩形来说，我们需要找到左边第一个比它低的高，和右边第一个比它低的高。

那么我们就可以写出暴力的算法来了。

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int q[N];

int main(int argc, char const *argv[])
{
   
    int n;
    while (scanf("%d",