【LeetCode】84. Largest Rectangle in Histogram 解いてみた【Hard】

はじめに

問題の概要

渡された配列で隣り合ってできた長方形の最大面積を返す

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

最初に考えた解き方

・隣り合う要素を引いて絶対値にしてそれを2つの要素の合計から引く。隣り合う長方形はこれで面積がでる。
・その隣にさらに要素がある場合はどう足すか？
＞その要素が絶対値より大きいなら成長は継続。
＞小さいなら前の要素までの長方形は成長停止。
＞＞がしかし、今比較している要素を高さとして長方形を成長させることが可能
＞＞＞これは次の要素が小さくなるまで成長継続
・途中で大きい要素が出てきたら成長途中の長方形が追加される
・長方形の最大値のスタック
・成長中の長方形の管理リスト：現在成長中の長方形の高さ：継続している長さ（幅）

流れ
1　リストが空なので、インプットの最初の要素をリストへ
2　2：1となる。これをつまり21
3　スタックが空なので投入
4　次のインプットを評価。リストのキー>=インプットなら
5　2：2となる
もしリストのキー>=インプットでないなら
5 キーをその値に更新
今回は1なので後者
2　スタックの一番上と比較。1：2なので値変わらず
次のインプットへ
配列の最後まで行ったらスタックが答え。
これスタックか？

class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        stack = []
        growing = []

        for h in heights:
            if growing:
                growH, growW = growing.pop()
                if growH < h:
                    growing.append([growH, growW])
                    growing.append([h, 0])
                else:
                    growing.append([h, growW])
                while len(growing) >= 2 and growing[-2][0] >= growing[-1][0]:
                    growing.pop()
                    prevH, prevW = growing.pop()
                    growing.append([h, prevW])
            else:
                growing.append([h, 0])

            for grow in growing:
                grow[1] += 1
                area = grow[0] * grow[1]
                if not stack:
                   stack.append(area)
                else:
                    if area > stack[-1]:
                        stack.append(area)

        return stack[-1]
       

何がよくなかったか？

3ケースだけタイムアウトしてしまった。
まあよくない点もあるが、hardを自力でほぼ解けたのはすごくうれしい
単純に惜しい。

解き方

高さが現在より下がったら面積計算して更新

これ一見すると低い高さでも繋がってるよね
と思う。
なら幅を計算する元を繋がりの大元にしちゃえばいいじゃんってこと

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        maxArea = 0
        stack = []  # pair: (index, height)

        for i, h in enumerate(heights):
            start = i
            while stack and stack[-1][1] > h:
                index, height = stack.pop()
                maxArea = max(maxArea, height * (i - index))
                start = index
            stack.append((start, h))

        for i, h in stack:
            maxArea = max(maxArea, h * (len(heights) - i))
        return maxArea

柔軟な考えが必要だ。

こうしたらもっといいけど不可能だなということもないのである。

参考資料

おわりに・まとめ

配列最初からどんな感じの流れで進んでいくか一個ずつ図を書いていったほうがいいな！