代碼隨想錄算法訓練營|第六十二天|84.柱状图中最大的矩形。刷题心得（c++）

目录

讀題

84.柱状图中最大的矩形

看完代码随想录之后的想法

84.柱状图中最大的矩形 - 實作

思路

單調棧橫向運算思路

Code

總結

自己实现过程中遇到哪些困难

今日收获，记录一下自己的学习时长

相關資料

---

讀題

84.柱状图中最大的矩形

看完代码随想录之后的想法

看完之後才知道為甚麼要接在接雨水的後面，整體的性質沒有差多少，但是就是反過來以及高度的計算上改為直接取當前最高的數值，但有一個操作很驚豔，就是前後加上0，因為在這題當中因為要取矩形所以要有前後的值進行計算，如果沒有這個前後加零的處理，就會需要再程式碼裡加上特殊處理，而前後加上0，就有點像是鏈表當中的虛頭節點一樣，加上之後就可以對於題目進行一致性的處理。

84.柱状图中最大的矩形 - 實作

思路

單調棧橫向運算思路

1. 數組前後加上0
2. 單調棧存放元素為數組下標
3. 單調棧性質為遞減
4. 當前元素對應的数組值與棧頂元素對應的数組值比較與處理
   1. 大於
      1. 將當前元素放入棧頂
   2. 等於
      1. pop棧頂元素
      2. 將當前元素放入棧頂
      3. 因為相等的話，如果比較最小值時，當前元素與棧頂元素相減 = 0 無論如何相乘都只會是0
   3. 小於
      1. 儲存棧頂元素
      2. pop棧頂
      3. 高度是
         1. 儲存棧頂元素的高
      4. 寬度是
         1. 當前元素減去目前棧頂元素再減去1
      5. result = max (h * w, result) 取最大
      6. 儲存當前元素到單調棧中
5. return result.

Code

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        st.push(0);
        int result = 0;
        for(int i = 1; i < heights.size(); i++) {
            if(heights[i] > heights[st.top()]){
                st.push(i);
            } else if (heights[i] == heights[st.top()]) {
                st.pop();
                st.push(i);
            } else {
                while(!st.empty() && heights[i] < heights[st.top()]) {
                    int mid = st.top();
                    st.pop();
                    if(!st.empty()) {
                        int h = heights[mid];
                        int right = st.top();
                        int left = i;
                        int w = left - right - 1;
                        result = max(h * w, result);
                    }
                }
                st.push(i);
            }
        }
        return result;
    }
};

總結

自己实现过程中遇到哪些困难

今天自己在想的時候沒有想出來，但是看完影片過後才豁然開朗，以及沒有想到前後加零的操作是如此方便，還需要對這些題目再進行了解與練習才行。

今日收获，记录一下自己的学习时长

今天大概學習1hr，主要是理解單調遞減以及怎麼去實現。

相關資料

● 今日学习的文章链接和视频链接

●  84.柱状图中最大的矩形

https://programmercarl.com/0084.柱状图中最大的矩形.html