LeetCodeWeekly240 C 1856. Maximum Subarray Min-Product ヒストグラム内の最大長方形の変形

題意

• 配列の連続した部分列の和 $ \times$ その区間の最小値　の最大値を求めよ

例: $[2,3,3,1,2]$の場合、[3,3]は和6 $times$ min3で18が答えとなる

こう考えた

ヒストグラムの最大長方形問題に帰着できます。次に図を示します。

上の絵が$[2,3,3]$を選択したとき。下の絵が$[3,3]$を選んだ時です。

ある要素$x$があった時、和がとられることを考えると、長さ$1$の長方形が$x$あると考えてよいです。

実装

さて、要素の数が十分に小さければ、図のようなヒストグラムを実際に配列としてつくって計算しても良いですが、大きい数だと配列が作れません。そのため、区間の和を$O(N)$で求められるように累積和を作ります。

ヒストグラムの最大化の面積を求める際、通常は

• ある部分の高さ $ \times $ 区間のindexの差
  を取りますが、今回は、

• ある部分の高さ $ \times $ 区間のindexの間の累積和
  を使います。

############################################
from collections import deque
from typing import Deque
from typing import List, Tuple
from pprint import pprint


class Rect:
    def __init__(self, height, pos):
        self.height = height
        self.pos = pos
def solve(h: [int]):
    # 拾い物 の　ヒストグラム最大化 ライブラリ
    stack: Deque[Rect] = deque()
    histogram = h + [0]
    max_area = 0

    # ここに累積和を足す
    import itertools
    def createSDAT(l):
        return list(itertools.accumulate(itertools.chain([0], l)))
    sdat = createSDAT(h)
    squery = lambda a, b: sdat[b] - sdat[a]  # query [a, b)

    for idx, height in enumerate(histogram):
        if not stack or stack[-1].height < height:
            stack.append(Rect(height=height, pos=idx))
        elif stack[-1].height > height:
            top = Rect(height=0, pos=0)
            while stack and stack[-1].height > height:
                top = stack.pop()
                # ここは通常、今の位置 - heightのposだが、ここを、その間のブロックの和にする
                #max_area = max(max_area, (idx - top.pos) * top.height)
                max_area = max(max_area, squery(top.pos, idx) * top.height)
            stack.append(Rect(height=height, pos=top.pos))
    return max_area
############################################
class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        res = solve(nums) % (10**9+7)
        return (res)