???個(gè)人主頁：@Sherry的成長(zhǎng)之路
??學(xué)習(xí)社區(qū)：Sherry的成長(zhǎng)之路（個(gè)人社區(qū)）
??專欄鏈接：練題
??長(zhǎng)路漫漫浩浩，萬事皆有期待

柱狀圖中最大的矩形

力扣題目鏈接

給定 n 個(gè)非負(fù)整數(shù)，用來表示柱狀圖中各個(gè)柱子的高度。每個(gè)柱子彼此相鄰，且寬度為 1 。

求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。

示例 1:

輸入：heights = [2,1,5,6,2,3]
輸出：10
解釋：最大的矩形為圖中紅色區(qū)域，面積為 10

示例 2：

輸入： heights = [2,4]
輸出： 4

思路

接雨水 中是找每個(gè)柱子左右兩邊第一個(gè)大于該柱子高度的柱子，而本題是找每個(gè)柱子左右兩邊第一個(gè)小于該柱子的柱子。

為什么這么說呢，因?yàn)槿缦聢D所示，高為3的柱子可以繼續(xù)往右邊蔓延擴(kuò)大面積，如果往左邊的話則長(zhǎng)度不夠

所以要找當(dāng)前柱子i左右兩側(cè)第一個(gè)小于他的柱子

動(dòng)態(tài)規(guī)劃

對(duì)于下標(biāo)i而言,能勾勒出的最大面積是什么?

以i為中心, 向左尋找第一個(gè)小于height[i]的下標(biāo)minLeftIndex, 向右尋找第一個(gè)小于height[i]的下標(biāo)minRightIndex, 即最大面積 = height[i] * (minRightIndex - minLeftIndex - 1)

如示例1中，求i=4的最大面積

正向遍歷數(shù)組 height 得到數(shù)組 minLeftIndex的每個(gè)索引值（第一小于當(dāng)前柱子高度的索引值），反向遍歷數(shù)組 height 得到數(shù)組minRightIndex（第一小于當(dāng)前柱子高度的索引值）

完整代碼：

public int largestRectangleArea(int[] heights) {
    int[] minLeftIndex = new int[heights.length];
    int[] minRightIndex = new int[heights.length];

    // 記錄每個(gè)柱子 左邊第一個(gè)小于該柱子的下標(biāo)
    minLeftIndex[0] = -1;
    for (int i = 1; i < heights.length; i++) {
        int left = i - 1;
        // 這里不是用if，而是不斷向左尋找的過程
        while (left >= 0 && heights[left] >= heights[i]) {
            left = minLeftIndex[left];
        }
        minLeftIndex[i] = left;
    }

    // 記錄每個(gè)柱子 右邊第一個(gè)小于該柱子的下標(biāo)
    minRightIndex[heights.length - 1] = heights.length;
    for (int i = heights.length - 2; i >= 0; i--) {
        int right = i + 1;
        // 這里不是用if，而是不斷向右尋找的過程
        while (right < heights.length && heights[right] >= heights[i]) {
            right = minRightIndex[right];
        }
        minRightIndex[i] = right;
    }

    // 求和
    int res = 0;
    for (int i = 0; i < heights.length; i++) {
        int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);
        res = Math.max(sum, res);
    }
    return res;
}

單調(diào)棧

本題是找每個(gè)柱子左右兩邊第一個(gè)小于該柱的柱子。這里就涉及到了單調(diào)棧很重要的性質(zhì)，就是單調(diào)棧里的順序，是從小到大還是從大到小。

在題解 接雨水 中接雨水的單調(diào)棧從棧頭（元素從棧頂彈出）到棧底的順序應(yīng)該是從小到大的順序。

那么因?yàn)楸绢}是要找每個(gè)柱子左右兩邊第一個(gè)小于該柱子的柱子，所以從棧頂?shù)綏５椎捻樞驊?yīng)該是從大到小的順序！

如圖所示的例子

當(dāng)我們遍歷到height[5]時(shí)，因?yàn)闂ｍ數(shù)綏５资菑拇蟮叫。琱eight[5]高度是小于棧頂元素的，所以就找到了此時(shí)的棧頂元素的左右第一個(gè)小于的柱子

此時(shí)大家應(yīng)該可以發(fā)現(xiàn)其實(shí)就是棧頂和棧頂?shù)南乱粋€(gè)元素以及要入棧的三個(gè)元素組成了我們要求最大面積的高度和寬度

剩下就是分析清楚如下三種情況：

情況一：當(dāng)前遍歷的元素heights[i]小于棧頂元素heights[st.top()]的情況
情況二：當(dāng)前遍歷的元素heights[i]等于棧頂元素heights[st.top()]的情況
情況三：當(dāng)前遍歷的元素heights[i]大于棧頂元素heights[st.top()]的情況
完整代碼：

public int largestRectangleArea(int[] heights) {
    Deque<Integer> stack = new LinkedList<>();
    // 數(shù)組擴(kuò)容，在頭和尾各加入一個(gè)元素
    int [] newHeights = new int[heights.length + 2];
    newHeights[0] = 0;
    newHeights[newHeights.length - 1] = 0;
    for (int index = 0; index < heights.length; index++){
        newHeights[index + 1] = heights[index];
    }

    // 之后就用newHeights計(jì)算
    stack.push(0);
    int res = 0;
    // 第一個(gè)元素已經(jīng)入棧，從下標(biāo)1開始
    for (int i = 1; i < newHeights.length; i++) {
        if (newHeights[i] > newHeights[stack.peek()]) {
            stack.push(i);
        }else if (newHeights[i] == newHeights[stack.peek()]) {
            stack.pop();
            stack.push(i);
        }else {
            // 我們要找到一個(gè)不小于newHeights[i]為止
            while (newHeights[i] < newHeights[stack.peek()]) {
                int mid = stack.peek(); // 中間柱子
                stack.pop();
                int left = stack.peek();
                int right = i;
                int w = right - left - 1;
                int h = newHeights[mid];
                res = Math.max(res, w * h);
            }
            stack.push(i);
        }
    }

    return res;
}

總結(jié)：

今天我們完成了柱狀圖中最大的矩形這道題，相關(guān)的思想需要多復(fù)習(xí)回顧。接下來，我們繼續(xù)進(jìn)行算法練習(xí)。希望我的文章和講解能對(duì)大家的學(xué)習(xí)提供一些幫助。

當(dāng)然，本文仍有許多不足之處，歡迎各位小伙伴們隨時(shí)私信交流、批評(píng)指正！我們下期見~

文章來源地址http://www.zghlxwxcb.cn/news/detail-814026.html

到了這里，關(guān)于【算法練習(xí)Day51】柱狀圖中最大的矩形的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！