##給定 n 個非負整數，用來表示柱狀圖中各個柱子的高度，每個柱子彼此相鄰，且寬度為 1 ，求在該柱狀圖中，能夠勾勒出來的矩形的最大面積，  以上是柱狀圖的示例，其中每個柱子的寬度為 1，給定的高度為 [2,1,5,6,2,3]，  圖中陰影部分為所能勾勒出的最大矩形面積，其面積為 10 個單位，
示例:
輸入: [2,1,5,6,2,3]
輸出: 10
思路
分治法：maxArea = max(當前區間minHeight*區間長度, max(minIndex左側區間子問題, minIndex右側區間子問題))
時間復雜度O(nlgn)，最壞O(n2)，空間復雜度O(n)，
代碼
class Solution {
public int calcArea(int[] heights, int start, int end) {
if(end < start) return 0;
int minIndex = start;
int minHeight = heights[start];
for(int i = start+1; i <= end; i++) {
if(heights[i] < minHeight) {
minHeight = heights[i];
minIndex = i;
}
}
return Math.max(minHeight*(end-start+1), Math.max(calcArea(heights,start,minIndex-1),calcArea(heights,minIndex+1,end)));
}
public int largestRectangleArea(int[] heights) {
return calcArea(heights, 0, heights.length-1);
}
}
筆記
存在堆疊方法，時間復雜度O(n)，空間復雜度O(n)，
鏈接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/91960.html
標籤：其他
上一篇：復雜度
下一篇：歸并排序演算法