- 分类：Stack
- 时间复杂度: O(n)
- 空间复杂度: O(n)
84. 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.
image.png
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
image.png
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：
class Solution:
def largestRectangleArea(self, heights: 'List[int]') -> 'int':
if heights==None or len(heights)==0:
return 0
res=0
j=0
stack=[]
left=0
right=0
heights.append(0)
heights.insert(0,0)
for i in range(0,len(heights)):
if len(stack)==0 or heights[i]>heights[stack[-1]]:
stack.append(i)
else:
right=i
j=stack[-1]
while len(stack)>1 and heights[stack[-1]]>heights[right]:
h=heights[stack.pop()]
left=stack[-1]
res=max(res,h*(right-left-1))
stack.append(i)
return res
代码2：
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
res = 0
if heights == None or len(heights)==0:
return res
stack = list()
stack.append(-1)
for i in range(len(heights)):
while(stack[-1]!=-1 and heights[stack[-1]]>=heights[i]):
h = heights[stack.pop()]
res = max(res, (i-stack[-1]-1)*h)
stack.append(i)
while (stack[-1]!=-1):
h = heights[stack.pop()]
res = max(res,(len(heights)-stack[-1]-1)*h)
return res
讨论：
1.看的youtube的篮子王的讲解
2.我是两边直接加两个0避免了还要比较边界条件的情况？？？代码可以更straight forward？？？
3.别忘了比完了之后那个地方的点是要加回去的orz
4.今天写代码是看youtube上一个happygirl的博主。感觉思路比篮子王清楚。还是个单调递增栈
