파이썬에서 히스토그램 아래에서 가장 큰 사각형 영역을 찾는 프로그램

히스토그램에서 막대의 높이를 나타내는 숫자 목록이 있다고 가정합니다. 막대 아래에서 형성할 수 있는 가장 큰 직사각형의 면적을 찾아야 합니다.

따라서 입력이 nums =[3, 2, 5, 7]

그러면 출력은 10이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• stk :=스택 및 초기에 -1 삽입
• 높이 끝에 0 삽입
• ans :=0
• 0에서 높이의 크기 범위에 있는 i에 대해 다음을 수행합니다.
  • hits[i]
  • h :=heights[stk의 상단] 및 stk에서 팝
  • w :=i - stk의 맨 위 - 1
  • ans :=ans 및 (h * w)의 최대값
• stk로 푸시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

class Solution:
   def solve(self, heights):
      stk = [-1]
      heights.append(0)
      ans = 0
      for i in range(len(heights)):
         while heights[i] < heights[stk[-1]]:
            h = heights[stk.pop()]
            w = i - stk[-1] - 1
            ans = max(ans, h * w)
         stk.append(i)
      return ans

ob = Solution()
nums = [3, 2, 5, 7]
print(ob.solve(nums))

입력

[3, 2, 5, 7]

출력

10