<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ??一站式輕松地調用各大LLM模型接口,支持GPT4、智譜、豆包、星火、月之暗面及文生圖、文生視頻 廣告
                # 0084. 柱狀圖中最大的矩形 ## 題目地址(84. 柱狀圖中最大的矩形) <https://leetcode-cn.com/problems/largest-rectangle-in-histogram/> ## 題目描述 給定 n 個非負整數,用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰,且寬度為 1 。 求在該柱狀圖中,能夠勾勒出來的矩形的最大面積。 ![](https://img.kancloud.cn/b1/c9/b1c9006c51f08aa560759b66f189d612_188x204.jpg) 以上是柱狀圖的示例,其中每個柱子的寬度為 1,給定的高度為 \[2,1,5,6,2,3\]。 ![](https://img.kancloud.cn/d1/dd/d1dd2f061718fcc505dc1362f324dc37_188x204.jpg) 圖中陰影部分為所能勾勒出的最大矩形面積,其面積為 10 個單位。 ``` <pre class="calibre18">``` 示例: 輸入:[2,1,5,6,2,3] 輸出:10 ``` ``` ## 前置知識 - 單調棧 ## 暴力枚舉 - 左右端點法(TLE) ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ### 思路 我們暴力嘗試`所有可能的矩形`。由于矩陣是二維圖形, 我我們可以使用`左右兩個端點來唯一確認一個矩陣`。因此我們使用雙層循環枚舉所有的可能性即可。 而矩形的面積等于`(右端點坐標 - 左端點坐標 + 1) * 最小的高度`,最小的高度我們可以在遍歷的時候順便求出。 ### 代碼 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">largestRectangleArea</span><span class="hljs-params">(self, heights: List[int])</span> -> int:</span> n, ans = len(heights), <span class="hljs-params">0</span> <span class="hljs-keyword">if</span> n != <span class="hljs-params">0</span>: ans = heights[<span class="hljs-params">0</span>] <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n): height = heights[i] <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(i, n): height = min(height, heights[j]) ans = max(ans, (j - i + <span class="hljs-params">1</span>) * height) <span class="hljs-keyword">return</span> ans ``` ``` **復雜度分析** - 時間復雜度:O(N2)O(N^2)O(N2) - 空間復雜度:O(1)O(1)O(1) ## 暴力枚舉 - 中心擴展法(TLE) ### 思路 我們仍然暴力嘗試`所有可能的矩形`。只不過我們這一次從中心向兩邊進行擴展。對于每一個 i,我們計算出其左邊第一個高度小于它的索引 p,同樣地,計算出右邊第一個高度小于它的索引 q。那么以 i 為最低點能夠構成的面積就是`(q - p - 1) * heights[i]`。 這種算法毫無疑問也是正確的。 我們證明一下,假設 f(i) 表示求以 i 為最低點的情況下,所能形成的最大矩陣面積。那么原問題轉化為`max(f(0), f(1), f(2), ..., f(n - 1))`。 具體算法如下: - 我們使用 l 和 r 數組。l\[i\] 表示 左邊第一個高度小于它的索引,r\[i\] 表示 右邊第一個高度小于它的索引。 - 我們從前往后求出 l,再從后往前計算出 r。 - 再次遍歷求出所有的可能面積,并取出最大的。 ### 代碼 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">largestRectangleArea</span><span class="hljs-params">(self, heights: List[int])</span> -> int:</span> n = len(heights) l, r, ans = [<span class="hljs-params">-1</span>] * n, [n] * n, <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, n): j = i - <span class="hljs-params">1</span> <span class="hljs-keyword">while</span> j >= <span class="hljs-params">0</span> <span class="hljs-keyword">and</span> heights[j] >= heights[i]: j -= <span class="hljs-params">1</span> l[i] = j <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n - <span class="hljs-params">2</span>, <span class="hljs-params">-1</span>, <span class="hljs-params">-1</span>): j = i + <span class="hljs-params">1</span> <span class="hljs-keyword">while</span> j < n <span class="hljs-keyword">and</span> heights[j] >= heights[i]: j += <span class="hljs-params">1</span> r[i] = j <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n): ans = max(ans, heights[i] * (r[i] - l[i] - <span class="hljs-params">1</span>)) <span class="hljs-keyword">return</span> ans ``` ``` **復雜度分析** - 時間復雜度:O(N2)O(N^2)O(N2) - 空間復雜度:O(N)O(N)O(N) ## 優化中心擴展法(Accepted) ### 思路 實際上我們內層循環沒必要一步一步移動,我們可以直接將`j -= 1` 改成 `j = l[j]`, `j += 1` 改成 `j = r[j]`。 ### 代碼 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">largestRectangleArea</span><span class="hljs-params">(self, heights: List[int])</span> -> int:</span> n = len(heights) l, r, ans = [<span class="hljs-params">-1</span>] * n, [n] * n, <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, n): j = i - <span class="hljs-params">1</span> <span class="hljs-keyword">while</span> j >= <span class="hljs-params">0</span> <span class="hljs-keyword">and</span> heights[j] >= heights[i]: j = l[j] l[i] = j <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n - <span class="hljs-params">2</span>, <span class="hljs-params">-1</span>, <span class="hljs-params">-1</span>): j = i + <span class="hljs-params">1</span> <span class="hljs-keyword">while</span> j < n <span class="hljs-keyword">and</span> heights[j] >= heights[i]: j = r[j] r[i] = j <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n): ans = max(ans, heights[i] * (r[i] - l[i] - <span class="hljs-params">1</span>)) <span class="hljs-keyword">return</span> ans ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:O(N)O(N)O(N) ## 單調棧(Accepted) ### 思路 實際上,讀完第二種方法的時候,你應該注意到了。我們的核心是求左邊第一個比 i 小的和右邊第一個比 i 小的。 如果你熟悉單調棧的話,那么應該會想到這是非常適合使用單調棧來處理的場景。 從左到右遍歷柱子,對于每一個柱子,我們想找到第一個高度小于它的柱子,那么我們就可以使用一個單調遞增棧來實現。 如果柱子大于棧頂的柱子,那么說明不是我們要找的柱子,我們把它塞進去繼續遍歷,如果比棧頂小,那么我們就找到了第一個小于的柱子。 **對于棧頂元素,其右邊第一個小于它的就是當前遍歷到的柱子,左邊第一個小于它的就是棧中下一個要被彈出的元素**,因此以當前棧頂為最小柱子的面積為**當前棧頂的柱子高度 \* (當前遍歷到的柱子索引 - 1 - 棧中下一個要被彈出的元素索引 - 1 + 1)** 這種方法只需要遍歷一次,并用一個棧。由于每一個元素最多進棧出棧一次,因此時間和空間復雜度都是O(N)O(N)O(N)。 為了統一算法邏輯,減少邊界處理,我在 heights 首尾添加了兩個哨兵元素,**這樣我們可以保證所有的柱子都會出棧**。 ### 代碼 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">largestRectangleArea</span><span class="hljs-params">(self, heights: List[int])</span> -> int:</span> n, heights, st, ans = len(heights), [<span class="hljs-params">0</span>] + heights + [<span class="hljs-params">0</span>], [], <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n + <span class="hljs-params">2</span>): <span class="hljs-keyword">while</span> st <span class="hljs-keyword">and</span> heights[st[<span class="hljs-params">-1</span>]] > heights[i]: ans = max(ans, heights[st.pop(<span class="hljs-params">-1</span>)] * (i - st[<span class="hljs-params">-1</span>] - <span class="hljs-params">1</span>)) st.append(i) <span class="hljs-keyword">return</span> ans ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:O(N)O(N)O(N) 2020-05-30 更新: 有的觀眾反應看不懂為啥需要兩個哨兵。 其實末尾的哨兵就是為了將棧清空,防止遍歷完成棧中還有沒參與運算的數據。 而前面的哨兵有什么用呢? 我這里把上面代碼進行了拆解: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">largestRectangleArea</span><span class="hljs-params">(self, heights: List[int])</span> -> int:</span> n, heights, st, ans = len(heights),[<span class="hljs-params">0</span>] + heights + [<span class="hljs-params">0</span>], [], <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n + <span class="hljs-params">2</span>): <span class="hljs-keyword">while</span> st <span class="hljs-keyword">and</span> heights[st[<span class="hljs-params">-1</span>]] > heights[i]: a = heights[st[<span class="hljs-params">-1</span>]] <span class="hljs-title"># 如果沒有前面的哨兵,這里可能會越界。</span> st.pop() ans = max(ans, a * (i - <span class="hljs-params">1</span> - st[<span class="hljs-params">-1</span>])) st.append(i) <span class="hljs-keyword">return</span> ans ``` ``` ## 相關題目 - [42.trapping-rain-water](https://github.com/azl397985856/leetcode/blob/master/problems/42.trapping-rain-water.md) 歡迎關注我的公眾號《腦洞前端》獲取更多更新鮮的 LeetCode 題解 ![](https://img.kancloud.cn/77/1d/771d6f53e2a51febbcb6fa97f2899ac3_1586x578.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看