Python의 히스토그램에서 가장 큰 사각형

히스토그램의 높이를 나타내는 하나의 정수 배열이 있다고 가정합니다. 각 막대에는 단위 너비가 있습니다. 다음과 같이 가장 큰 면적의 직사각형을 찾아야 합니다. -

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

• 스택 생성, i :=0, ans :=0

  설정

• 동안 나는 <높이의 크기, then

  • 스택에 0개의 요소가 있거나 스택 상단 요소의 높이가 <=height[i]인 경우

    • i를 스택에 삽입하고 i를 1만큼 증가

  • 그렇지 않으면 -

    • x :=스택 상단 요소, 스택에서 삭제

    • 높이 :=높이[x]

    • temp :=height * (i * stack[-1] – 1) 스택이 비어 있지 않으면 temp :=height * i

    • ans :=ans 및 temp의 최대값

• 스택이 비어 있지 않은 동안 -

  • x :=스택 맨 위 요소

  • 높이 :=높이[x], 스택에서 삭제

  • temp :=높이 * 높이의 길이 – 스택 상단 요소 – 스택이 비어 있을 때 1, 그렇지 않으면 temp :=높이의 길이

  • ans :=ans 및 temp의 최대값

• 반환

예

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

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