Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 히스토그램에서 가장 큰 직사각형 넓이 구하기 — 스택 활용 완벽 가이드

정수 배열로 히스토그램의 각 막대 높이가 주어졌다고 가정해 보겠습니다. 각 막대의 너비는 1로 고정되어 있습니다. 이때 우리가 구해야 할 것은 히스토그램 안에 포함될 수 있는 가장 큰 직사각형의 넓이입니다.

예를 들어, 높이 배열 [2, 1, 5, 7, 3, 2]가 주어지면 인접한 막대들을 조합하여 만들 수 있는 최대 직사각형의 넓이는 12가 됩니다.

문제 해결 접근 방식

모든 막대 조합을 일일이 확인하는 브루트 포스 방식은 시간이 오래 걸립니다. 대신 스택(Stack) 자료구조를 활용하면 O(n)의 시간 복잡도로 효율적으로 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다. 스택에는 막대의 인덱스를 저장하며, 현재 막대보다 높은(또는 같은) 막대들이 연속으로 쌓여 있는 동안에는 계속 인덱스를 추가합니다. 더 낮은 막대를 만나면 그동안 쌓인 막대들을 하나씩 꺼내며, 각 막대를 기준으로 만들 수 있는 최대 넓이를 계산합니다.

알고리즘 단계

  • 스택을 생성하고, i := 0, ans := 0으로 초기화합니다.

  • i가 heights 배열의 길이보다 작은 동안 반복합니다.

    • 스택이 비어 있거나 스택 최상위 요소의 높이가 heights[i]보다 작거나 같으면 → i를 스택에 추가하고, i를 1 증가시킵니다.

    • 그렇지 않으면 →
      x := 스택 최상위 요소를 꺼냅니다.
      height := heights[x]
      스택이 비어 있지 않으면 temp := height × (i − stack[-1] − 1), 비어 있으면 temp := height × i
      ans := max(ans, temp)

  • 스택이 빌 때까지 반복합니다.

    • x := 스택 최상위 요소를 꺼내고, height := heights[x]
      스택이 비어 있지 않으면 temp := height × (배열 길이 − stack[-1] − 1), 비어 있으면 temp := height × 배열 길이
      ans := max(ans, temp)

  • 최종적으로 ans를 반환합니다.

예제 코드

아래 파이썬 구현을 통해 알고리즘을 더 명확하게 이해할 수 있습니다.

class Solution(object):
   def largestRectangleArea(self, heights):
      stack = []
      i = 0
      ans = 0
      while i < len(heights):
         if len(stack) == 0 or heights[stack[-1]] <= heights[i]:
            stack.append(i)
            i += 1
         else:
            x = stack[-1]
            stack.pop()
            height = heights[x]
            temp = height * (i - stack[-1] - 1) if len(stack) != 0 else height * i
            ans = max(ans, temp)
      while len(stack) > 0:
         x = stack[-1]
         height = heights[x]
         stack.pop()
         temp = height * (len(heights) - stack[-1] - 1) if len(stack) != 0 else height * len(heights)
         ans = max(ans, temp)
      return ans

ob = Solution()
print(ob.largestRectangleArea([2, 1, 5, 7, 3, 2]))

실행 결과

입력:

[2, 1, 5, 7, 3, 2]

출력:

12

마무리 정리

이 알고리즘은 각 막대를 한 번씩만 스택에 넣고 빼기 때문에 전체 시간 복잡도는 O(n), 공간 복잡도는 스택 저장 공간만큼 O(n)입니다. 배열 끝까지 탐색한 후 스택에 남아 있는 막대들에 대해 마지막으로 넓이를 계산하는 두 번째 while 루프가 핵심 포인트이므로, 이 부분을 놓치지 않도록 주의하세요.