Pythonのヒストグラムで最大の長方形

これを解決するには、次の手順に従います-

• スタックを作成し、i：=0、ans：=0

  を設定します

• <高さのサイズなら

  • スタックの要素が0であるか、スタックの最上位要素の高さが<=height [i]の場合、

    • iをスタックに挿入し、iを1増やします

  • それ以外の場合-

    • x：=スタックの最上位要素、スタックから削除します。

    • height：=heights [x]

    • temp：=height *（i * stack [-1] – 1）スタックが空でない場合、それ以外の場合はtemp：=height * i

    • ans：=ansとtempの最大値

• スタックが空でない間-

  • x：=スタックトップ要素

  • height：=height [x]、スタックから削除

  • temp：=高さ*高さの長さ–スタックトップ要素–スタックが空でない場合は1、それ以外の場合はtemp：=高さの長さ

  • ans：=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