訓練營打卡Day64

文章目錄

• 訓練營打卡Day64
• • 題134：[84. 柱狀圖中最大的矩形](https://leetcode.cn/problems/largest-rectangle-in-histogram/)
  • • 思路
    • 代碼

題134：84. 柱狀圖中最大的矩形

思路

• 首先，它會在數組的頭和尾加上一個高度為 0 的柱子，這是為了友善處理在棧中的每一個柱子。
• 然後，對于數組中的每一個柱子，通過循環彈出棧頂的柱子，直到棧頂的柱子高度小于等于目前柱子。每一次彈出操作，都可以計算出目前彈出柱子作為高度的矩形的最大面積。然後，把目前柱子入棧，以便它可以作為下一個柱子的高度。
• 最後，傳回最大矩形面積。

代碼

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++) {
            while (heights[i] < heights[st.top()]) {
                int mid = st.top();
                st.pop();
                int w = i - st.top() - 1;
                int h = heights[mid];
                result = max(result, w * h);
            }
            st.push(i);
        }
        return result;
    }
};