mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-05 16:36:41 +08:00
34 lines
1.5 KiB
Markdown
34 lines
1.5 KiB
Markdown
# [84. Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/)
|
|
|
|
## 题目
|
|
|
|
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
|
|
|
|

|
|
|
|
|
|
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
|
|
|
|

|
|
|
|
|
|
The largest rectangle is shown in the shaded area, which has area = 10 unit.
|
|
|
|
|
|
|
|
Example:
|
|
|
|
```c
|
|
Input: [2,1,5,6,2,3]
|
|
Output: 10
|
|
```
|
|
|
|
|
|
## 题目大意
|
|
|
|
给出每个直方图的高度,要求在这些直方图之中找到面积最大的矩形,输出矩形的面积。
|
|
|
|
|
|
## 解题思路
|
|
|
|
用单调栈依次保存直方图的高度下标,一旦出现高度比栈顶元素小的情况就取出栈顶元素,单独计算一下这个栈顶元素的矩形的高度。然后停在这里(外层循环中的 i--,再 ++,就相当于停在这里了),继续取出当前最大栈顶的前一个元素,即连续弹出 2 个最大的,以稍小的一个作为矩形的边,宽就是 2 计算面积…………如果停在这里的下标代表的高度一直比栈里面的元素小,就一直弹出,取出最后一个比当前下标大的高度作为矩形的边。宽就是最后一个比当前下标大的高度和当前下标 i 的差值。计算出面积以后不断的更新 maxArea 即可。 |