solution.md

# 柱状图中最大的矩形

<p>给定 <em>n</em> 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。</p><p>求在该柱状图中，能够勾勒出来的矩形的最大面积。</p><p>&nbsp;</p><p><img src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0084.Largest%20Rectangle%20in%20Histogram/images/histogram.png"></p><p><small>以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为&nbsp;<code>[2,1,5,6,2,3]</code>。</small></p><p>&nbsp;</p><p><img src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0084.Largest%20Rectangle%20in%20Histogram/images/histogram_area.png"></p><p><small>图中阴影部分为所能勾勒出的最大矩形面积，其面积为&nbsp;<code>10</code>&nbsp;个单位。</small></p><p>&nbsp;</p><p><strong>示例:</strong></p><pre><strong>输入:</strong> [2,1,5,6,2,3]<strong><br />输出:</strong> 10</pre>

以下程序实现了这一功能，请你填补空白处内容：

```python
class Solution(object):
	def largestRectangleArea(self, heights):
		"""
		:type heights: List[int]
		:rtype: int
		"""
		largest_rectangle = 0
		ls = len(heights)
		stack = [-1]
		top, pos = 0, 0
		for pos in range(ls):
			while top > 0 and heights[stack[top]] > heights[pos]:
				_____________________________
				top -= 1
				stack.pop()
			stack.append(pos)
			top += 1
		while top > 0:
			largest_rectangle = max(largest_rectangle, heights[stack[top]] * (ls - stack[top - 1] - 1))
			top -= 1
		return largest_rectangle
if __name__ == "__main__":
	s = Solution()
	print (s.largestRectangleArea([2,1,5,6,2,3]))
```

## template

```python
class Solution(object):
	def largestRectangleArea(self, heights):
		"""
		:type heights: List[int]
		:rtype: int
		"""
		largest_rectangle = 0
		ls = len(heights)
		stack = [-1]
		top, pos = 0, 0
		for pos in range(ls):
			while top > 0 and heights[stack[top]] > heights[pos]:
				largest_rectangle = max(largest_rectangle, heights[stack[top]] * (pos - stack[top - 1] - 1))
				top -= 1
				stack.pop()
			stack.append(pos)
			top += 1
		while top > 0:
			largest_rectangle = max(largest_rectangle, heights[stack[top]] * (ls - stack[top - 1] - 1))
			top -= 1
		return largest_rectangle
if __name__ == "__main__":
	s = Solution()
	print (s.largestRectangleArea([2,1,5,6,2,3]))
```

## 答案

```python
largest_rectangle = max(largest_rectangle, heights[stack[top]] * (pos - stack[top - 1] - 1))
```

## 选项

### A

```python
largest_rectangle = max(largest_rectangle, heights[stack[top]] * (pos - stack[top] - 1))
```

### B

```python
largest_rectangle = max(largest_rectangle, heights[stack[top]] * (pos - stack[top + 1] - 1))

```

### C

```python
largest_rectangle = max(largest_rectangle, heights[stack[top]] * (pos - stack[top - 1] + 1))
```