릿코드 84 - Largest Rectangle in Histogram

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        tmp = [heights[0]]
        cnt = [1]
        for i in range(1, len(heights)) : 
            if heights[i] == tmp[-1] : 
                cnt[-1] += 1
            else : 
                tmp.append(heights[i])
                cnt.append(1)
        heights = tmp
        
        max = 0
        for idx, item in enumerate(heights) : 
            tmp = cnt[idx]
            for i in range(idx + 1, len(heights)) : 
                if heights[i] < item : 
                    break
                tmp += cnt[i]
            for i in range(idx - 1, -1, -1) : 
                if heights[i] < item : 
                    break
                tmp += cnt[i]
            tmp = tmp * item
            max = max if max > tmp else tmp
        return max

n^2 의 무식한 방법이다.. 역시나 시간은 거의 최하위권...ㅎ 더 좋은 방법을 고민해봐야겠다

순회하면서 하나를 잡고 왼쪽 체크하고 오른쪽 체크하고 (오른쪽 끝 index - 왼쪽 끝 index) * height[i] 로 계산한다.

 

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

거의 두배가까이 줄인 코드. i의 역할은 계산해야하는 오른쪽 인덱스를 가리키고 st[-1]의 역할은 왼쪽 끝을 가리킨다. 오른쪽 끝 값인 i 에서 st[-1]을 뺀 값을 heitght[n] 에다가 곱해주면 되는 계산방식. 1을 더 빼줘야하는 이유는 i가 다음 인덱스를 가리키고 있기 때문에 1을 빼줘야 제대로 값이 나온다.