LeetCode_單調棧_困難_84.柱狀圖中最大的矩形

目錄

• 1.題目
• 2.思路
• 3.代碼實作（Java）

1.題目

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

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

示例 1：

輸入：heights = [2,1,5,6,2,3]

輸出：10

解釋：最大的矩形為圖中紅色區域，面積為 10

示例 2：

輸入：heights = [2,4]

輸出：4

提示：

1 <= heights.length <=105

0 <= heights[i] <= 104

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/largest-rectangle-in-histogram

2.思路

（1）單調棧

所謂單調棧，即元素值單調遞增或單調遞減的棧。單調棧這種資料結構，通常應用在一維數組上，如果需要解決的問題與前後元素之間的大小關系有關的話，此時可以考慮使用單調棧。例如在本題中，前後柱子的高度會影響最大矩形面積的計算。

（2）暴力窮舉法

使用兩層 for 循環窮舉出所有的矩陣，然後儲存最大面積并傳回即可，但是該方法的時間複雜度較高，為O(n2)，是以在LeetCode中運作時存在逾時現象，并不能通過。

3.代碼實作（Java）

//（1）單調棧
public int largestRectangleArea(int[] heights) {
    int length=heights.length;
    //定義最大的矩形面積，初始值為0
    int maxArea=0;
    //定義單調棧，此處存儲數組元素的下标，保證下标對應的值從棧底到棧頂逐漸遞增
    Stack<Integer> stack = new Stack<>();
    for(int i=0;i<length;i++){
        //棧不為空，并且目前元素值小于等于數組下标為棧頂元素的值
        while(!stack.isEmpty() && heights[i]<=heights[stack.peek()]){
            //将棧頂元素出棧
            int j=stack.pop();
            //求左邊界
            int left=stack.isEmpty()?-1:stack.peek();
            //矩形面積=(右邊界-左邊界-1)*高度
            int curArea = (i-left-1)*heights[j];
            maxArea = Math.max(maxArea, curArea);
        }
        //将目前下标加入到棧中
        stack.push(i);
    }
    //求整個高度單調遞增的柱子所能勾勒出來的矩形的最大面積
    while(!stack.isEmpty()){
        int j=stack.pop();
        int left=stack.isEmpty()?-1:stack.peek();
        //此時的右邊界就是數組長度
        int curArea=(heights.length-left-1)*heights[j];
        maxArea = Math.max(maxArea, curArea);
    }
    return maxArea;
}
           

//（2）暴力窮舉法
public int largestRectangleArea(int[] heights) {
    int len=heights.length;
    int maxArea=heights[0];
    int minLength;
    //暴力窮舉法
    for(int i=0;i<len;i++){
        minLength=heights[i];
        for(int j=i;j<len;j++){
            //求出目前矩陣的寬
            int width=(j>i)?(j-i+1):1;
            //求出目前矩陣的長，它由最小的柱子高度決定
            minLength=(heights[j]<minLength)?heights[j]:minLength;
            //求出目前矩陣的面積
            int curArea=width*minLength;
            //儲存目前得到的最大矩陣面積
            maxArea=(maxArea>curArea)?maxArea:curArea;
        }
    }
    //傳回最大面積
    return maxArea;
}