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.
Example:
Input: [2,1,5,6,2,3] Output: 10
My code:
import numpy as np
class Solution:
def largestRectangleArea(self, heights):
stack = []
stack.append(-1)
maxarea = 0
for i in range( len(heights) ):
while stack[-1] != -1 and heights[stack[-1]] >= heights[i]:
#print('i %d'%i)
#print(stack)
maxarea = max(maxarea, heights[stack.pop()] * (i - stack[-1] - 1))
#print(maxarea)
stack.append(i)
while stack[-1] != -1:
maxarea = max(maxarea, heights[stack.pop()] * (len(heights) - stack[-1] -1))
return maxarea
def largestRectangleArea2(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
#O n^2 time
self.matrix=np.zeros([len(heights),len(heights)])-1
result=self.area(heights,0,len(heights)-1)
return int(result)
def area(self,heights,i,j):
if i>j:
return 0
if self.matrix[i,j]!=-1:
return self.matrix[i,j]
if i==j:
self.matrix[i,i]=heights[i]
return self.matrix[i,i]
result1=min(heights[i:j+1])*(j+1-i)
result2=self.area(heights,i+1,j)
result3=self.area(heights,i,j-1)
self.matrix[i,j]=max([result1,result2,result3])
return self.matrix[i,j]
Solution: https://leetcode.com/problems/largest-rectangle-in-histogram/