Leetcode 84. Largest Rectangle in Histogram

Seawolf

1. 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.
   
2. 
   
3. 
   
4. 
   
5. 
   
6. Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
   
7. 
   
8. 
   
9. 
   
10. 
    
11. The largest rectangle is shown in the shaded area, which has area = 10 unit.
    
12. 
    
13. 
    
14. 
    
15. Example:
    
16. 
    
17. Input: [2,1,5,6,2,3]
    
18. Output: 10

复制代码

1. class Solution:
   
2.     def largestRectangleArea(self, heights: List[int]) -> int:
   
3.         if heights == None or len(heights) == 0:
   
4.             return 0
   
5.         res = 0
   
6.         stack = []
   
7.         for i in range(len(heights) + 1):
   
8.             if i == len(heights):
   
9.                 curt = -1
   
10.             else:
    
11.                 curt = heights[i]
    
12.             while stack and curt <= heights[stack[-1]]:
    
13.                 h = heights[stack.pop()]
    
14.                 if len(stack) != 0:
    
15.                     w = i - stack[-1] - 1
    
16.                 else:
    
17.                     w = i
    
18.                 res = max(res, w * h)
    
19.             stack.append(i)
    
20.         return res

复制代码