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

Difficulty: interview

Starter code:

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        

Solutions:
class Solution:
     def largestRectangleArea(self, heights):
         """
         :type heights: List[int]
         :rtype: int
         """
         
         if not heights:
             return 0
         stack = [0]
         heights.append(0)
         # print(heights)
         max_area = 0
         for i in range(len(heights)):
             # print(stack)
             if heights[i] >= stack[-1]:
                 stack.append(heights[i])
             else:
                 k = len(stack) - 1
                 count = 0
                 while heights[i] < stack[k] and k >= 0:
                     count += 1
                     # print(count)
                     # print(stack[k])
                     area = count * stack[k]
                     if max_area < area:
                         max_area = area
                     k -= 1
                     # print(max_area)
                 stack = stack[:-count] + [heights[i],] * (count + 1)
                 # print((count + 1) * stack[k])
                 # if max_area < (count + 1) * heights[i]:
                     # max_area = (count + 1) * heights[i]
         return max_area


class Solution:
 
 	def largestRectangleArea(self, heights):
 		"""
 		:type heights: List[int]
 		:rtype: int
 		"""
 		if not heights:
 			return 0
 
 		max_area = 0
 		stack = []
 		i = 0
 		while i < len(heights):
 			while i < len(heights) and (len(stack) == 0 or heights[i] > heights[stack[-1]]):
 				stack.append(i)
 				i += 1
 			tmp = stack.pop()
 			if stack:
 				area = heights[tmp] * (i - stack[-1] - 1)
 			else:
 				area = heights[tmp] * i
 			max_area = max(area, max_area)
 		while stack:
 			tmp = stack.pop()
 			if stack:
 				area = heights[tmp] * (i - stack[-1] - 1)
 			else:
 				area = heights[tmp] * i
 			max_area = max(area, max_area)
 
 		return max_area


class Solution:
     def largestRectangleArea(self, heights):
         """
         :type heights: List[int]
         :rtype: int
         """
         stack = list()
         helper_stack = list()
 
         max_area = 0
         for i in heights:
             if not stack:
                 stack.append(i)
             else:
                 if i >= stack[-1]:
                     stack.append(i)
                 else:
                     width = 0
                     helper_stack.append(i)
                     while(stack and stack[-1]>i):
                         width += 1
                         height = stack.pop()
                         helper_stack.append(i)
                         max_area = max(max_area,height*width)
                     while helper_stack:
                         stack.append(helper_stack.pop())
             # print(stack)
         width = 0
         # print(stack)
         while stack:
             width += 1
             height = stack.pop()
             max_area = max(max_area,height*width)
 
         return max_area

class Solution:
     def largestRectangleArea(self, heights):
         """
         :type heights: List[int]
         :rtype: int
         """
         stk = []
         res = 0
         for i in range(len(heights)):
             if len(stk) == 0 or heights[i] >= heights[stk[-1]]:
                 stk.append(i)
             else:
                 end_p = stk[-1]
                 while len(stk) > 0 and heights[stk[-1]] >= heights[i]:
                     start_p = stk.pop()
                     res = max(res, (end_p - start_p + 1) * heights[start_p])
                 res = max(res, heights[i] * (i - start_p + 1))
                 heights[start_p] = heights[i]
                 stk.append(start_p)
                 stk.append(i)
             #print(res, stk)
         
         if len(stk) > 0:
             end_p = stk[-1]
             while len(stk) > 0:
                 start_p = stk.pop()
                 res = max(res, (end_p - start_p + 1) * heights[start_p])
                 #print(res)
         
         
         return res
                 
                 
                     
             
         


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

class Solution:
     def largestRectangleArea(self, heights):
         n = len(heights)
         if n == 0:
             return 0
         left = [i for i in range(n)]
 
         right = [i+1 for i in range(n)]
         print(heights)
         for i in range(1, n):
             # indicates the next value to compare
             cur = i - 1
             # import pdb
             # pdb.set_trace()
             while cur >= 0 and heights[cur] >= heights[i]:
                 left[i] = left[cur]
                 cur = left[cur] - 1
 
         for j in range(n-1, -1, -1):
             cur = j + 1
             while cur < n and heights[cur] >= heights[j]:
                 # import pdb
                 # pdb.set_trace()
                 right[j] = right[cur]
                 cur = right[cur]
 
         print(left)
         print(right)
         max_val = 0
         for i in range(n):
             tmp = heights[i] * (right[i] - left[i])
             if max_val < tmp:
                 max_val = tmp
 
         return max_val


class Solution:
     def largestRectangleArea(self, heights):
         """
         :type heights: List[int]
         :rtype: int
         """
         
         # # sol1: mono_inc stack
         # stack = [(-1, 0)]
         # res = 0
         # for i, h in enumerate(heights + [0]):
         #     while stack[-1][1] > h:
         #         H = stack.pop()[1]
         #         W = i - stack[-1][0] - 1
         #         res = max(res, H*W)
         #     stack.append((i, h))
         # return res
         
         # sol2: left/right(include self) higher neighbors
         if not heights:
             return 0
         N = len(heights)
         left, right = [1]*N, [1]*N
         for i in range(1, N):
             j = i - 1
             while j >= 0 and heights[j] >= heights[i]:
                 left[i] += left[j]
                 j -= left[j]
         for i in range(N - 1, -1, -1): # 注意降序要写完整 -1, -1
             j = i + 1
             while j <= N - 1 and heights[j] >= heights[i]:
                 right[i] += right[j]
                 j += right[j]
         return max((l+r-1)*h for l,r,h in zip(left,right,heights))

class Solution:
     def largestRectangleArea(self, heights):
         """
         :type heights: List[int]
         :rtype: int
         """
         stack = []
         ans = 0
         heights += [-1]
         for i in range(len(heights)):
             left = i
             while 1:
                 if len(stack)==0:
                     stack.append((heights[i], left))
                     break
                 if stack[-1][0]<heights[i]:
                     stack.append((heights[i], left))
                     break
                 elif stack[-1][0]==heights[i]:
                     break
                 else:
                     ans = (i-stack[-1][1])*stack[-1][0] if (i-stack[-1][1])*stack[-1][0]>ans else ans
                     left = stack[-1][1]
                     del stack[-1]
         return ans