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.

My Answer 1: Output Limit Exceeded (90 / 96 test cases passed.)

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        if len(heights) == 0:
            return
        
        # 숫자가 한 종류만 있을 경우 높이가 모두 같으므로 바로 계산해서 리턴
        if len(set(heights)) == 1:
            return heights[0] * len(heights)
        
        # heights 의 최댓값 or 최솟값의 넓이 중 최댓값을 디폴트로 가짐
        result = max(max(heights), min(heights)*len(heights))
        
        for i in range(len(heights)):
            # 0 은 무시
            if heights[i] == 0:
                continue
                
            h = heights[i]
            area = h
            
            # 현재 숫자의 왼쪽부분 넓이 구하기
            for j in range(i-1, -1, -1):
                if heights[j] >= heights[i]:
                    area += h
                else:
                    break
                    
            # 현재 숫자의 오른쪽부분 넓이 구하기
            for j in range(i+1, len(heights)):
                if heights[j] >= heights[i]:
                    area += h
                else:
                    break
                    
            # area = 왼쪽+오른쪽 넓이를 합친 값
            result = max(result, area)
        
        return result

heights[i] 왼쪽과 오른쪽의 가능한 넓이들을 각각 구하고 더해서 최댓값을 구하는 식으로 함

하지만 아웃풋 리밋~~

Solution 1: Runtime: 756 ms - 35.95% / Memory Usage: 27.6 MB - 20.13%

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        ## RC ##
        ## APPROACH : MONOTONOUS INCREASING STACK ##
        ## Similar to Leetcode: 1475. Final Prices With a Special Discount in a Shop ##
        ## Similar to Leetcode: 907. Sum Of Subarray Minimums ##
        ## Similar to Leetcode: 85. maximum Rectangle ##
        ## Similar to Leetcode: 402. Remove K Digits ##
        ## Similar to Leetcode: 456. 132 Pattern ##
        ## Similar to Leetcode: 1063. Number Of Valid Subarrays ##
        ## Similar to Leetcode: 739. Daily Temperatures ##
        ## Similar to Leetcode: 1019. Next Greater Node In LinkedList ##
        
        ## LOGIC ##
        ## 1. Before Solving this problem, go through Monotone stack.
        ## 2. Using Monotone Stack we can solve 1) Next Greater Element 2) Next Smaller Element 3) Prev Greater Element 4) Prev Smaller Element
        ## 3. Using 'NSE' Monotone Stack concept, we can find width of rectangles, height obviously will be the minimum of those. Thus we can calculate the area
        ## 4. As we are using NSE concept, adding 0 to the end, will make sure that stack is EMPTY at the end. ( so all the areas can be calculated while popping )
        
        heights.append(0)
        stack = [-1]
        ans = 0
        for i in range(len(heights)):
            while heights[i] < heights[stack[-1]]:
                height = heights[stack.pop()]
                width = i - stack[-1] - 1
                ans = max(ans, height * width)
            stack.append(i)
        heights.pop()
        return ans

stack 을 사용하는 거고.. 코드가 돌아가는 건 알겠는데 왜 이렇게 하는지는 모르겠음..^^

스택에 인덱스를 하나하나 저장해주고
stack[-1] 이 현재 숫자보다 큰 값이면, stack[-1] 을 세로로 잡고
가능한 가로*세로 넓이 구해서 max 값으로 update