[Leetcode] largest-rectangle-in-histogram

質問リンク

[問題を理解する]

以下の高さを与える場合、最大の矩形幅を求めるのが問題です.
この問題に対してbroot forceで解決すればOが発生する(n^2).
条件は1<=hightsです.length<=10^5なのでタイムアウトが発生するので、より効率的に処理する必要があります.

[アクセス]

状況を分けて整理する.

まず、ブルートフォスでアプローチすると、以下のようになります.
5から読み始めると、5を始点とし、5以上の棒に順番に近づき、幅=5×2=10となる.つまり、5より小さい2と3は必要ありません.
6人時点は6 X 1=6.
2の場合は3が2より大きいので2 X 4=8です.(5と6は2未満)
3人の場合は3 X 1=3です.
すなわち、最大幅は10です.
ある図形の視点における最大矩形の高さを求める場合、それより小さい欄の情報は必要ありません.(
すなわち,それを最大限に金属化して解く.3つの状況を考えなさい.
今の棒を基準に...
1.前より大きいバーが表示されます

ロッドであれば、以前に出現したロッドの高さを含めながら使用を継続する.

より前の欄の場合は

である.

以前のロッドより小さい場合、以前のロッドは現在のロッドを基準に高さを使用しません.従って、前のレバーを含む最も広い矩形の幅を求め、容器から除去する.このとき取り除くと現在入っている位置が変わります.(幅を求める)

以前のレバーと同じなら、そのままスキップします.

その上で、私たちはこれについて研究しました.

以下の高さのヒストグラムがある場合は、指数別に表示します.
index=0～2
max size=0(計算されていません)
stack=[{0(始点)、3(高さ)]
index=3の場合
index 3より認知点が高い(高さ2より大きい)前のすべての内容を削除し、幅を計算します.
max_size=9,
stack=[{0(始点),2(高さ)]:位置を除去点に変換します.
index=4の場合
index 4の認知点よりも高い古いものをすべて取り除き、幅を計算します.
2(前のインデックスの高さ)*(4(現在のインデックス位置)-0(前のインデックスの高さの開始インデックス)=8.すなわち、max sizeの9より小さいため、変更されない.
stack=[{0(始点),1(高さ)]:位置を削除点に変更します.
**読み終わったら
容器に残っているものをすべて計算し、max sizeを比較して削除します.
stack[{0(始点)、1(高さ)}]の処理が必要です.
(5(長さ)-0(始点)X 1(高さ)=5
このときmax size未満が9の場合は変化しない.

[実装]

#include <bits/stdc++.h>
using namespace std;
#define Pair pair<int, int>
#define pos first
#define height second
class Solution
{
public:
    int largestRectangleArea(vector<int> &heights)
    {
        int __maxSize = 0, pos_length = heights.size();
        stack<Pair> st;
        for (int pos = 0; pos < pos_length; pos++)
        {
            int cur_height = heights[pos];
            if (!st.empty() && cur_height == st.top().height)
                continue;
            else
            {
                int next_pos = pos;
                while (!st.empty() && st.top().height > cur_height)
                {
                    Pair next = st.top();
                    next_pos = next.pos;
                    st.pop();
                    // int before = st.empty() ? 0 : st.top().pos;
                    __maxSize = max(__maxSize, (pos - next_pos) * next.height);
                }
                if (!st.empty() && cur_height == st.top().height)
                    continue;
                st.push({next_pos, cur_height});
            }
        }
        while (!st.empty())
        {
            Pair next = st.top();
            st.pop();
            __maxSize = max(__maxSize, (pos_length - next.pos) * next.height);
        }
        return __maxSize;
    }
};
int main()
{
    vector<int> vec({2, 1, 5, 6, 2, 3});
    vector<int> vec2({5, 4, 1, 2});
    Solution *solution = new Solution();
    cout << solution->largestRectangleArea(vec) << endl;
    cout << solution->largestRectangleArea(vec2) << endl;
}