---
title: "直方图中最大的矩形"
created: 2025-11-28
tags:
  - 算法
---

# 直方图中最大的矩形

## 题目 [直方图中最大的矩形](https://www.acwing.com/problem/content/description/133/)

![[image-2961668c.png]]

## 思路分析

矩形面积不过是宽乘高

很容易可以发现 高其实是被限制着的

![[image-3a3bf0ed.png]]

于是可以想到枚举每一根柱子 以它的高作为整个矩形的高 来去找最大的宽

![[image-6fabcae7.png]]

最大的宽被什么限制住了呢？

显然是左右最近的一个小于当前高度的那根

可以对每个柱子都用一次双指针往左右去探 但显然这样很笨 浪费时间

对于这种 找左边最近的小于当前元素的位置 的模型

显然是单调栈

也如图看到了 为了避免判断边界情况 可以在最左和最右填一根高度为-1的柱子

对于找左边的最近的最小的柱子 用的直接是模板

找右边其实就从右边开始做就好了

最后可以找到每根柱子i的左边界l[i] 右边界r[i] 还有它的读入的高h[i]

面积就是r[i]-1 - l[i]+1 +1 \* h[i]

用max维护即可

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=100010;

LL h[N];

int l[N],r[N];

int s[N];

int n;

int main()

{

    while(cin>>n && n){

        for(int i=1;i<=n;i++){

            cin>>h[i];

        }

        h[0]=h[n+1]=-1;

        int top=0;

        s[0]=0;

        for(int i=1;i<=n;i++){

            while(h[s[top]]>=h[i])

                top--;

            l[i]=s[top];

            s[++top]=i;

        }

        top=0;

        s[0]=n+1;

        for(int i=n;i>=1;i--){

            while(h[s[top]]>=h[i])

                top--;

            r[i]=s[top];

            s[++top]=i;

        }

        LL res=0;

        for(int i=1;i<=n;i++){

            res=max(res,(LL)h[i]*((r[i]-1)-(l[i]+1)+1));

        }

        cout<<res<<endl;

    }

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/栈与队列相关模型/单调栈/最长连续子序列|最长连续子序列]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/栈与队列相关模型/单调队列|单调队列]]