[Leetcode]84. Largest Rectangle in Histogram(x)

1. problem : 

https://leetcode.com/problems/largest-rectangle-in-histogram/description/

 

2. solution 1 :

class Solution:
	def largestRectangleArea(self,heights : List[int]) -> int:
    	stack = []
        index = 0 
        max_area = 0 
        
        while index < len(heights):
        	if not stack or stack[-1] <= heights[index]:
            	index += 1 
                stack.append(index)
            else:
            	top_of_stack = stack.pop() 
                width = index if not stack else index - stack[-1] - 1 
                max_area = max(max_area,heights[top_of_stack]*width) 
        while stack:
        	top_of_stack = stack.pop() 
            width = index if not stack else index - stack[-1] - 1 
            max_area = max(max_area, height[top_of_stack] * width) 
        return max_area

상당히 어렵다. stack을 쓰는 문제.. 외우자.