# 84. Largest Rectangle in Histogram 柱状图中最大的矩形

@TOC

## # 题目描述

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:

``````Input: [2,1,5,6,2,3]
Output: 10
``````

## # 解题方法

### # 单调栈

1. 如果后面新来的元素高度比栈顶元素高，那么需要入栈，因为面积最大的元素会出现在后面。
2. 如果后面新来的元素高度比栈顶元素小，那么需要弹出栈里的元素，并且，每次弹出的时候都要对计算目前的宽度，相乘得到面积。

``````class Solution(object):
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
stack = list()
res = 0
heights.append(0)
N = len(heights)
for i in range(N):
if not stack or heights[i] > heights[stack[-1]]:
stack.append(i)
else:
while stack and heights[i] <= heights[stack[-1]]:
h = heights[stack[-1]]
stack.pop()
w = i if not stack else i - stack[-1] - 1
res = max(res, h * w)
stack.append(i)
return res
``````

https://www.cnblogs.com/boring09/p/4231906.html

## # 日期

2018 年 10 月 9 日 —— 今天降温7度，注意保暖