示例:
输入: [2,1,5,6,2,3]
输出: 10
思路
分治法:maxArea = max(当前区间minHeight*区间长度, max(minIndex左侧区间子问题, minIndex右侧区间子问题))
时间复杂度O(nlgn),最坏O(n²),空间复杂度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