kniost

谁怕，一蓑烟雨任平生

0%

LeetCode 84. Largest Rectangle in Histogram

发表于 更新于 分类于
本文字数： 5k 阅读时长 ≈ 5 分钟
LeetCode 84. Largest Rectangle in Histogram

84. Largest Rectangle in Histogram

Difficulty:: Hard

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:

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

Solution

Language: Java

暴力法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
      public int largestRectangleArea(int[] heights) {
            if (heights == null || heights.length == 0) {
                  return 0;
           }
            int largestArea = 0;
            for (int i = 0; i < heights.length; i++) {
                  int minHeight = Integer.MAX_VALUE;
                  for (int j = i; j < heights.length; j++) {
                        minHeight = Math.min(heights[j], minHeight);
                        largestArea = Math.max(largestArea, minHeight * (j - i + 1));
                 }
           }
            return largestArea;
     }
}

分治法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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[i] < heights[minIndex]) {
                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);
    }
}

单调栈

维护一个单调递增栈，逐个将元素 push 到栈里。push 进去之前先把 >= 自己的元素 pop 出来。
每次从栈中 pop 出一个数的时候，就找到了往左数比它小的第一个数（当前栈顶）和往右数比它小的第一个数（即将入栈的数），
从而可以计算出这两个数中间的部分宽度 * 被pop出的数，就是以这个被pop出来的数为最低的那个直方向两边展开的最大矩阵面积。
因为要计算两个数中间的宽度，因此放在 stack 里的是每个数的下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        Deque<Integer> stack = new ArrayDeque<>();
        int max = 0;
        for (int i = 0; i <= heights.length; i++) {
            int cur = i == heights.length ? -1 : heights[i];
            while (!stack.isEmpty() && heights[stack.peek()] > cur) {
                int h = heights[stack.pop()];
                int w = stack.isEmpty() ? i : i - stack.peek() - 1;
                max = Math.max(max, h * w);
            }
            stack.push(i);
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
## [84\. Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/description/)

Difficulty:: **Hard**


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.

![](https://assets.leetcode.com/uploads/2018/10/12/histogram.png)  
<small style="display: inline;">Above is a histogram where width of each bar is 1, given height = `[2,1,5,6,2,3]`.</small>

![](https://assets.leetcode.com/uploads/2018/10/12/histogram_area.png)  
<small style="display: inline;">The largest rectangle is shown in the shaded area, which has area = `10` unit.</small>

**Example:**

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


### Solution

Language: **Java**

#### 暴力法
```java
class Solution {
      public int largestRectangleArea(int[] heights) {
            if (heights == null || heights.length == 0) {
                  return 0;
           }
            int largestArea = 0;
            for (int i = 0; i < heights.length; i++) {
                  int minHeight = Integer.MAX_VALUE;
                  for (int j = i; j < heights.length; j++) {
                        minHeight = Math.min(heights[j], minHeight);
                        largestArea = Math.max(largestArea, minHeight * (j - i + 1));
                 }
           }
            return largestArea;
     }
}

分治法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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[i] < heights[minIndex]) {
                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);
    }
}

单调栈

维护一个单调递增栈，逐个将元素 push 到栈里。push 进去之前先把 >= 自己的元素 pop 出来。
每次从栈中 pop 出一个数的时候，就找到了往左数比它小的第一个数（当前栈顶）和往右数比它小的第一个数（即将入栈的数），
从而可以计算出这两个数中间的部分宽度 * 被pop出的数，就是以这个被pop出来的数为最低的那个直方向两边展开的最大矩阵面积。
因为要计算两个数中间的宽度，因此放在 stack 里的是每个数的下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        Deque<Integer> stack = new ArrayDeque<>();
        int max = 0;
        for (int i = 0; i <= heights.length; i++) {
            int cur = i == heights.length ? -1 : heights[i];
            while (!stack.isEmpty() && heights[stack.peek()] > cur) {
                int h = heights[stack.pop()];
                int w = stack.isEmpty() ? i : i - stack.peek() - 1;
                max = Math.max(max, h * w);
            }
            stack.push(i);
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        Deque<Integer> stack = new ArrayDeque<>();
        int max = 0;
        stack.push(-1);
        for (int i = 0; i < heights.length; i++) {
            while (stack.peek() != -1 && heights[i] < heights[stack.peek()]) {
                max = Math.max(max, heights[stack.pop()] * (i - stack.peek() - 1));
            }
            stack.push(i);
        }
        while (stack.peek() != -1) {
            max = Math.max(max, heights[stack.pop()] * (heights.length - stack.peek() - 1));
        }
        return max;
    }
}

```