Pythonのヒストグラムの下で最大の長方形の領域を見つけるプログラム

ヒストグラムの棒の高さを表す数値のリストがあるとします。バーの下に形成できる最大の長方形の領域を見つける必要があります。

したがって、入力がnums =[3、2、5、7]

その場合、出力は10になります

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

• stk：=スタックで、最初に-1を挿入します
• 高さの最後に0を挿入
• ans：=0
• 0から高さのサイズまでの範囲のiについては、
  • heights [i]
  • h：=heights [top of stk] and pop from 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