[leetcode] 84. Largest Rectangle in Histogle解題レポート

タイトルリンク:https://leetcode.com/problems/largest-rectangle-in-histogram/
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height =  [2,1,5,6,2,3] .
The largest rectangle is shown in the shaded area, which has area =  10  unit.
For example, Given height =  [2,1,5,6,2,3] , return  10 .
考え方:この問題の基本的な思想はすべてのbarを最低点とし、彼より小さいbarや境界に出会うまで左右に遍歴することである.これにより、このbarが最低点の矩形面積が見つかります.すべてのbarを巡回すると、最大の矩形面積が見つかります.しかし、彼より小さいbarを左右に巡る時間の複雑さはO(n)であり、すべてのbarを加えると、総時間の複雑さはO(n*n)となり、すべてのデータを通過することはできない.従って,barの左右境界を探すアルゴリズムをより時間的複雑度の低いアルゴリズムを探す必要がある.stackを用いて時間の複雑さをO(n)に低減できる極めて巧みな設計方法がネット上に流れている.
このアルゴリズムの考え方は,配列中の要素の位置を保存する増分スタックを維持することである.このようにスタックの中でそれぞれの左のbarは自分より小さいので、左は天然に境界があり、つまり左の境界は左のbarです.height配列を繰り返し、height配列をスタックに入れるときに、現在の要素height[i]がスタックトップ要素よりも小さい場合、スタックトップ要素の右境界を見つけます.従って,左右の境界は既に見つかっており,O(1)の時間複雑度で見つかったので,スタックトップ要素を最低barとする矩形面積を計算できるようになった.スタックトップ要素をスタックから出すことができます.これにより、スタックごとに1つの要素、すなわち、この要素を最低点とする矩形面積が計算される.最終スタックが空になったとき,すべてのbarを最低点とする矩形面積を計算した.すべての要素がスタックから出ることを保証するために、height配列に最後に0を追加します.1つの要素がスタックから出るには、彼より小さい要素、すなわち右境界に遭遇しなければならないからです.
コードは次のとおりです.

class Solution {
public:
    int largestRectangleArea(vector& heights) {
        if(heights.size() ==0) return 0;
        heights.push_back(0);
        int len = heights.size(), ans = 0;
        stack st;
        for(int i = 0; i < len; i++)
        {
            while(!st.empty() && heights[i] < heights[st.top()])
            {
                auto val = st.top();
                st.pop();
                ans = max(ans, heights[val]*(i-1-(st.empty()?-1:st.top())));
            }
            st.push(i);
        }
        return ans;
    }
};