0%

leetcode Largest Rectangle in Histogram || leetcode Maximal Rectangle

本次题解包括

  • 84. Largest Rectangle in Histogram
  • 85. Maximal Rectangle

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.

img
img

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

img
img

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

For example, Given heights = [2,1,5,6,2,3], return 10.

题目地址:leetcode Largest Rectangle in Histogram

题目大意:给定数组height表示矩形的高度,求矩形围城的矩形区域最大面积。

思路:很容易想到O(n^2)方法,枚举起始,枚举结束。。。用栈的话可以有O(N)的方法。

用一个栈来维护一个递增序列的下标:

  1. 如果当前的高度不大于栈顶的元素高度,那么pop并更新直到比当前元素的高度小的时候。更新的时候需要注意的是,用栈顶的高度作为计算的高(这样做的原因是栈顶的高一定比到当前下标i之间的元素来的小,这样就相当于有了起点和终点,这个区间可以采用当前栈顶的高)所以宽度为i - 1 - q.top() (i不计算在内,故-1,)当q为空时候,说明当前高度是“有史以来”最小的,宽度应该为i。
  2. 否则把当前下标入栈。
  3. 当全部元素都过完一遍,但是栈不为空的时候,可以想象为height[n]==int_min的时候,按第一步进行更新。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
int largestRectangleArea(vector<int> &height) {
stack<int> q;
int n = height.size();
int ans = 0, curArea;
for (int i = 0; i < n; i++){
while (!q.empty() && height[q.top()] >= height[i]){
int h = height[q.top()];
q.pop();
int width = q.empty() ? i : i - 1 - q.top();
if (width * h > ans) ans = h*width;
}
q.push(i);
}

while (!q.empty()){
int h = height[q.top()];
q.pop();
int width = q.empty() ? n : n - 1 - q.top();
if (width * h > ans) ans = h * width;
}
return ans;
}
};

 

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
q = []
ans = 0
for i, height in enumerate(heights):
while q and heights[q[-1]] > height:
h = heights[q.pop()]
w = i - 1 - q[-1] if q else i
ans = max(ans, h * w)
q.append(i)
n = len(heights)
while q:
h = heights[q.pop()]
w = n - 1 - q[-1] if q else n
ans = max(ans, h * w)
return ans

 


85. Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

题目地址:leetcode Maximal Rectangle

题目大意:给定由0和1组成的矩阵,求由1构成的最大矩阵。如:

0110

1010为2.

思路:设dp[i][j]为(i,j)这列上连续1的个数,然后就相当于求给定矩形高度,求最大矩形面积。。

你就秒懂之一图流:

(到最后一行可以转化为给定高度为:0,1,2,3的矩形, 求其最大矩形面积)

QQ截图20150226231110
QQ截图20150226231110

就是上面那一题。

leetcode两题放一起真是用心良苦。。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
int largestRectangleArea(vector<int>& heights) {
stack<int> q;
int ans = 0, n = heights.size();
for (int i = 0; i < n; ++i) {
while (!q.empty() && heights[i] <= heights[q.top()]) {
int h = heights[q.top()];
q.pop();
int w = q.empty() ? i : i - 1 - q.top();
if (w * h > ans) ans = w * h;
}
q.push(i);
}
while (!q.empty()) {
int h = heights[q.top()];
q.pop();
int w = q.empty() ? n : n - 1 - q.top();
if (w * h > ans) ans = w * h;
}
return ans;
}

public:
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;

vector<int> pre_sum(matrix[0].size(), 0);
int ans = 0;
for (int i = 0; i < matrix.size(); ++i) {
for (int j = 0; j < matrix[0].size(); ++j) {
pre_sum[j] = matrix[i][j] == '0' ? 0 : pre_sum[j] + 1;
}
ans = max(ans, largestRectangleArea(pre_sum));
}
return ans;
}
};

 

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution(object):
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
ans = 0
q = []
for i in range(len(heights)):
while q and heights[i] <= heights[q[-1]]:
h = heights[q.pop()]
w = i - 1 - q[-1] if q else i
ans = max(ans, h * w)
q.append(i)

while q:
h = heights[q.pop()]
w = len(heights) - 1 - q[-1] if q else len(heights)
ans = max(ans, h * w)
return ans

def maximalRectangle(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if not matrix or not matrix[0]: return 0
pre_sum = [0] * len(matrix[0])
ans = 0

for i in range(len(matrix)):
for j in range(len(matrix[0])):
pre_sum[j] = 0 if matrix[i][j] == '0' else pre_sum[j] + 1
ans = max(ans, self.largestRectangleArea(pre_sum))
return ans

 

本文是leetcode如下的题解

  • 84. Largest Rectangle in Histogram
  • 85. Maximal Rectangle

更多题解可以查看: https://www.hrwhisper.me/leetcode-algorithm-solution/

请我喝杯咖啡吧~