[LeetCode 풀이/python] 84. Largest Rectangle in Histogram (hard)

문제 설명: 정수 배열 heights 는 히스토그램 막대의 높이를 나타내며, 각 막대의 너비는 1 이다. 이 때, 히스토그램에서 가장 큰 직사각형의 넓이를 리턴하시오.

 

(Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.)

 

예시 1)

입력: heights = [2,1,5,6,2,3]  -->  출력: 10

설명: 가장 큰 직사각형은 붉게 나타난 영역으로, 각 막대의 너비가 1 이므로 총 넓이 10 을 갖는다.

 

예시 2)

입력: heights = [2,4] -->  출력: 4

 

제한 조건:

• 1 <= heights.length <= 10^5
• 0 <= heights[i] <= 10^4

 

------ * ------ * ------ * ------

 

[풀이 1안]  -- not a solution

• 접근법
  • heights 의 각 인덱스에 대해 해당 위치에서부터 배열(히스토그램) 의 맨 끝까지로 너비를 한 칸씩 증가시키며 각각에 대한 최대 넓이를 구함
  • 결과적으로 각 인덱스에 해당하는 막대를 직사각형의 왼쪽 모서리로 하여 만들 때의 최대 넓이를 저장한 후, 이들 중 가장 큰 수를 최종 결과로 리턴 

 

• 코드 구현

def largestRectangleArea(heights: List[int]) -> int:
    res = set()
    for i in range(len(heights)):
        ss = self.max_subset(heights, i)
        res.add(ss)
    return max(res)
            
def max_subset(heights, i):
    hei = heights[i]
    res = 0
    for j in range(i, len(heights)):
        hei = min(hei, heights[j])
        tmp_res = (j-i+1) * hei
        res = max(tmp_res, res)
    return res

 

• 결과
  • height 배열을 선형적으로 탐색하면서 각각에 대해 (len(heights) - i) 범위를 순회하므로, 총 시간복잡도가 O(n^2)
  • 예시 케이스는 대부분 통과하나 submit 시 Time Limit Exceed Error 발생 ㅜㅜ 
  • 현재 코드로는 불필요한 비교 계산이 많이 이루어지게 됨 --> 효율성 개선이 필요하다...!

 

 

[풀이 2안]  -- w/solution peeping

• 접근법
  • 영 모르겠어서 discussion 을 참고했으며 인상 깊은 접근법이라 기록 겸 리뷰 'ㅇ' )
  • 배열 heights 를 선형적으로 탐색하되,
    • 1) 별도 stack 을 만들어 이전에 지나온 막대의 높이들의 인덱스를 저장해 두고,
    • 2) i 번째 탐색에서 heights[i] 를 높이로 하는 직사각형을 만드는 것이 아니라(!), i 번째 이전 인덱스의 (stack 에 쌓여 있는) 막대 높이를 이용하여 직사각형을 만듦
    • 3) 선형 탐색 과정에서 모든 i 에 대해 넓이를 계산하는 것이 아니라, i 번째 인덱스의 막대 높이 값이 이전보다 (stack 의 맨 위에 있는 값보다) 더 작아졌을 때에만 계산 & 비교를 진행함 
  • 결국 구하고자 하는 것은 max area 인데, 2) 와 같이 i 번째 인덱스에서 i 이전까지의 높이를 이용해 넓이를 구하게 하는 구조에서, 3) 과 같이 i 번째 인덱스에 해당하는 높이가 이전보다 더 작아질 경우 해당 높이 (global) max area 값이 될 수 없으므로 while height[i] < height[stack[-1]] 인 경우에만 직사각형 넓이를 계산하면 됨
    • 넓이 계산을 위해 각 막대의 높이 값(인덱스) 을 stack.pop() 으로 가져옴으로써 불필요한 중복 계산을 피함
  • 해당 로직 적용을 위해 heights.append(0) & stack = [-1] 으로 초기 셋팅하는 것도 중요한 포인트...!

 

• 코드 구현

def largestRectangleArea(heights):
    heights.append(0)
    stack = [-1]
    res = 0
    
    for i in range(len(heights)):
        while heights[i] < heights[stack[-1]]:
            h = heights[stack.pop()]
            w = i - stack[-1] - 1
            res = max(res, h * w)
        stack.append(i)
    heights.pop()
    
    return res

 

• 결과
  • 배열 heights 를 선형 탐색하되, heights[i] < heights[stack[-1]] 인 상황에서만 비교 & 계산을 진행하면, 결과적으로 각 heights[i] 를 오른쪽 모서리로 하는 (가장 큰 넓이의) 직사각형에 대해서만 넓이 값을 구하게 되므로, 총 O(n)
  • 이런 생각은 도대체 어떻게 하는거야........ ㅜ_ㅜ