【問題描述】[困難]
給定 n 個非負整數，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。以上是柱狀圖的示例，其中每個柱子的寬度為 1，給定的高度為 [2,1,5,6,2,3]。圖中陰影部分為所能勾勒出的最大矩形面積，其面積為 10 個單位。輸入: [2,1,5,6,2,3]
輸出: 10來源：力扣（LeetCode）
【解答思路】
1. 暴力
可以枚舉以每個柱形為高度的最大矩形的面積。
具體來說就是：依次遍歷柱形的高度，對于每一個高度分別向兩邊擴散，求出以當前高度為矩形的最大寬度多少。
時間復雜度：O(N^2) 空間復雜度：O(1)
public class Solution {public int largestRectangleArea(int[] heights
) {int len
= heights
.length
;if (len
== 0) {return 0;}int res
= 0;for (int i
= 0; i
< len
; i
++) {int left
= i
;int curHeight
= heights
[i
];while (left
> 0 && heights
[left
- 1] >= curHeight
) {left
--;}int right
= i
;while (right
< len
- 1 && heights
[right
+ 1] >= curHeight
) {right
++;}int width
= right
- left
+ 1;res
= Math
.max(res
, width
* curHeight
);}return res
;}
}
2. 單調棧
時間復雜度：O(N) 空間復雜度：O(N)
import java
.util
.ArrayDeque
;
import java
.util
.Deque
;public class Solution {public int largestRectangleArea(int[] heights
) {int len
= heights
.length
;if (len
== 0) {return 0;}if (len
== 1) {return heights
[0];}int area
= 0;Deque
<Integer> stack
= new ArrayDeque<>();for (int i
= 0; i
< len
; i
++) {while (!stack
.isEmpty() && heights
[stack
.peekLast()] > heights
[i
]){int height
= heights
[stack
.removeLast()];while (!stack
.isEmpty() && heights
[stack
.peekLast()] == height
){stack
.removeLast();}int width
;if (stack
.isEmpty()){width
= i
;} else {width
= i
- stack
.peekLast() - 1;}area
= Math
.max(area
, width
* height
);}stack
.addLast(i
);}
while (!stack
.isEmpty()){int height
= heights
[stack
.removeLast()];while (!stack
.isEmpty() && heights
[stack
.peekLast()] == height
){stack
.removeLast();}int width
;if (stack
.isEmpty()){width
= len
;} else {width
= len
- stack
.peekLast() - 1;}area
= Math
.max(area
, width
* height
);}return area
;}
}
3. 哨兵思想+單調棧
時間復雜度：O(N) 空間復雜度：O(N)
import java
.util
.ArrayDeque
;
import java
.util
.Deque
;public class Solution {public int largestRectangleArea(int[] heights
) {int len
= heights
.length
;if (len
== 0) {return 0;}if (len
== 1) {return heights
[0];}int area
= 0;int[] newHeights
= new int[len
+ 2];for (int i
= 0; i
< len
; i
++) {newHeights
[i
+ 1] = heights
[i
];}len
+= 2;heights
= newHeights
;Deque
<Integer> stack
= new ArrayDeque<>();stack
.addLast(0);for (int i
= 1; i
< len
; i
++) {while (heights
[stack
.peekLast()] > heights
[i
]) {int height
= heights
[stack
.removeLast()];int width
= i
- stack
.peekLast() - 1;area
= Math
.max(area
, width
* height
);}stack
.addLast(i
);}return area
;}
}
【總結】
1.算法思想
其實可以把這個想象成鋸木板，如果木板都是遞增的那我很開心，如果突然遇到一塊木板i矮了一截，那我就先找之前最戳出來的一塊（其實就是第i-1塊），計算一下這個木板單獨的面積，然后把它鋸成次高的，這是因為我之后的計算都再也用不著這塊木板本身的高度了。再然后如果發覺次高的仍然比現在這個i木板高，那我繼續單獨計算這個次高木板的面積（應該是第i-1和i-2塊），再把它倆鋸短。直到發覺不需要鋸就比第i塊矮了，那我繼續開開心心往右找更高的。當然為了避免到了最后一直都是遞增的，所以可以在最后加一塊高度為0的木板。
這個算法的關鍵點是把那些戳出來的木板早點單獨拎出來計算，然后就用不著這個值了。
2.對于 使用 Java 的朋友， Stack 改用 Deque 的問題，參考文章：https://mp.weixin.qq.com/s/Ba8jrULf8NJbENK6WGrVWg
3.單調棧
出棧都要做的判斷!stack.isEmpty()
4.哨兵思想
轉載鏈接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/bao-li-jie-fa-zhan-by-liweiwei1419/
參考鏈接：
https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/xiang-jie-dan-diao-zhan-bi-xu-miao-dong-by-sweetie/
總結
以上是生活随笔為你收集整理的[Leedcode][JAVA][第84题][柱状图中最大的矩形][暴力][单调栈]的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
