0
Software Development

## 【Day 29】#84 - Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example:

``````Input: [2,1,5,6,2,3]
Output: 10
``````

## 解析

• 最小高度乘以全長
• 最小高度左側的最大面積（不包括最小高度）
• 最小高度右側的最大面積（不包括最小高度）

## 解法一(Brute Force)

`````` public class Solution {
public int largestRectangleArea(int[] heights) {
int maxarea = 0;
int bars = heights.length;
for (int i = 0; i < bars; i++) {
int minheight = Integer.MAX_VALUE;
for (int j = i; j < bars; j++) {
minheight = Math.min(minheight, heights[j]);
maxarea = Math.max(maxarea, minheight * (j - i + 1));
}
}
return maxarea;
}
}
``````

## 解法二(Divide and Conquer)

``````public class Solution {
public int calculateArea(int[] heights, int start, int end) {
if (start > end) {
return 0;
}
int minindex = start;
for (int i = start; i <= end; i++)
if (heights[minindex] > heights[i])
minindex = i;
return Math.max(heights[minindex] * (end - start + 1), Math.max(calculateArea(heights, start, minindex - 1), calculateArea(heights, minindex + 1, end)));
}
public int largestRectangleArea(int[] heights) {
return calculateArea(heights, 0, heights.length - 1);
}
}
``````

## 備註

LeetCode刷題日記30

### 1 則留言

1
obelisk0114
iT邦新手 5 級 ‧ 2019-12-15 18:32:44