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


<!--

## 技術記事のタイトル

【LeetCode】〇〇 解いてみた

最も伝えたいこと。
簡潔かつ分かりやすく過不足ないタイトルを考えましょう。

### 【 】(墨付き括弧)

タグ

LeetCode 競技プログラミング Python 

- 【言語やサービス】
    - 例1.【Python】すぐにpytestで単体テストを実行するまでの手順
- 【言いたいこと】
    - 例1.【必見】Objectはどこに消えた？
- 【前提】
    - 例1.【個人開発】○○を○○できるサービスをリリースしました
    - 例2.【初心者向け】Reactとはそもそも何なのか説明します
- 【続き物の番号】
    - 例1.【2024年版】新入社員向け研修資料を公開します
    - 例2.【環境構築編】Windows11でPythonを実行するまで

【前提】詳しいタイトル【言語やサービス】のように、複数を併用するパターンもあります。

-->

## はじめに
<!--
何についての記事なのか、誰に向けた記事なのかを簡単に説明しましょう。
-->

### 問題の概要
<!--
読んだら何がわかるようになるのか、何ができるようになるのかを書きましょう。
-->

![スクリーンショット 2025-02-09 19.33.19.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3913183/d876bbca-2df1-b3f7-a31a-2013c1de874e.png)

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

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となる。これを*つまり2*1
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を自力でほぼ解けたのはすごくうれしい
単純に惜しい。

## 解き方
<!--
章全体の要約や、何について書くのかをここに書きます。
記事が長い時や資料として作るときは番号を振ることをおすすめします。
章を増やすときは章から項までをコピーしてください。
-->




### 高さが現在より下がったら面積計算して更新
これ一見すると低い高さでも繋がってるよね
と思う。
なら幅を計算する元を繋がりの大元にしちゃえばいいじゃんってこと
<!--
記事の主要な部分です。ここに思い思いの内容を書いていってください。

画像やGIFがあると分かりやすいです。
画像があるとUIが変わったとしても読者がアタリをつけて対応しやすくなります。

コードを記載する場合は必ずコードブロックを使いましょう。
バッククオート3つで囲んでください。
```python:表示名

    print('Hello World')
    
```
-->
```
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
```



#### 柔軟な考えが必要だ。
<!--
より詳細な内容を書いたり、事例を挙げたりするときに使います。
- 節の内容の列挙
- 節の補足事項
- 例外
-->
こうしたらもっといいけど不可能だなということもないのである。


## 参考資料
<!--

https://qiita.com

[リンク1](https://qiita.com)
-->

https://leetcode.com/problems/largest-rectangle-in-histogram/description/

## おわりに・まとめ
<!--
どちらかを書きます。あってもなくても良いです。
-->

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