Leetcode 84. 柱状図の中で最大の矩形Largest Rectangle in Histogram

https://leetcode-cn.com/probl...
タイムアウトする方法:
にじゅうサイクル
最も簡単な考え方では,時間複雑度O(n^2)がタイムアウトする(最後にタイムアウトコードを添付する)
ぶんかつアルゴリズム
まず、現在の配列の最小要素を見つけます.
では、答えは3つの状況にあります.

は最小要素を含む、高さは最小要素の高さであり、長さは区間全体

である.

は最小要素を含まず、最下要素の左側(再帰左半区間)

である.

は最小要素を含まず、最下要素に辺(再帰右半区間)

がある.
この方法の平均時間複雑度はO(nlogn)である.
しかし最悪時間複雑度はO(n^2)でもタイムアウト(最後にタイムアウトコード付)
正しい解法
前から後ろに遍歴し、プロセス中に増加したスタックを維持します.
次がスタックトップ要素より大きい場合は、直接スタックに入ります.
小さい場合は、スタック内の大きな要素をすべて飛び出し、計算高さはポップアップされた要素の高さであり、幅は現在の要素からスタックトップ要素の間です.
ポップアップ要素の高さを高さとし、現在の位置とスタックトップ要素の位置間の距離を幅とすることができるのはなぜですか?スタックは増加するので、ポップアップ要素よりも高い要素はスタックにあるに違いありません.スタックの上部には、この要素に最も近い(要素よりも低い要素)に違いありません.言い換えれば、それらの間の要素の高さは要素よりも大きいです.

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        hs = [0] + heights + [0]
        s = []
        ans = 0
        for i, h in enumerate(hs):
            while s and hs[s[-1]] > h:
                j = s.pop()
                ans = max(ans, hs[j] * (i-s[-1]-1))
            s.append(i)
        return ans

タイムアウトコード
タイムアウトコードの二重ループ

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        maxa = 0
        for i in range(len(heights)):
            minh = heights[i]
            for j in range(i, len(heights)):
                minh = min(minh, heights[j])
                maxa = max(maxa, minh * (j-i+1))
        return maxa

タイムアウトコードの一分割

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        def solve(l, r, d):
            if l >= r: return 0
            if l == r-1: return heights[l]
            min_i = l
            min_h = heights[l]
            for i, h in enumerate(heights[1+l:r]):
                if h < min_h:
                    min_h = h
                    min_i = i+l+1
            return max(min_h * (r - l), solve(l, min_i, d+1), solve(min_i+1, r, d+1))
        return solve(0, len(heights), 0)

リファレンス
私のブログへようこそ:https://codeplot.top/私のブログのブラシの分類:https://codeplot.top/categories/%E5%88%B7%E9%A2%98/