LeetCode -- 84 and 85

本篇博客讨论LeetCode 8485

LeetCode 84

Description

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
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

img
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

考虑一种特殊情况,height是一个单调的数列,例如:

$$height = (1, 2, 4, 5, 8, 10)$$

那么显然

$$ans = \mathop{\arg \max}_{1\leq i\leq n} h[i] \times (n - i + 1)​$$

所以只需要维护一个单调队列queue即可。

如果在这个单调队列末尾欲加入数字$x$,为了维持queue的单调性,将末尾比$x$大的数字弹出,每次弹出一个数字$y$,记得使用$y$来更新ans

最后使用queue来更新ans。为了简化编程,可以在$height$末尾加入-1

Python Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
stack = []
heights.append(-1)
ret = 0
for i in range(len(heights)):
while len(stack) > 0 and heights[i] <= heights[stack[-1]]:
h = heights[stack.pop()]
w = i if len(stack) == 0 else i - 1 - stack[-1]
# print(h, w)
ret = max(ret, h * w)
stack.append(i)
return ret

LeetCode 85

Description

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

Example:

1
2
3
4
5
6
7
8
Input:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
Output: 6

Solution

直接对问题求解复杂度较高,但是可以将问题转化一下:

如果矩阵的下边界是第i行,那么问题就与上一题十分相似了。具体来说,将(i,j)以上的连续的1的数目作为height[j]的话,问题就完全变成LeetCode 84了。

Python Code:

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
class Solution:
def largestRectangleArea(self, heights: List[int], n: int) -> int:
stack = []
if len(heights) <= n:
heights.append(-1)
else:
heights[n] = -1

ret = 0
for i in range(n + 1):
while len(stack) > 0 and heights[i] <= heights[stack[-1]]:
h = heights[stack.pop()]
w = i if len(stack) == 0 else i - 1 - stack[-1]
# print(h, w)
ret = max(ret, h * w)
stack.append(i)
return ret

def maximalRectangle(self, matrix: List[List[str]]) -> int:
m = len(matrix)
if m == 0:
return 0
n = len(matrix[0])

heights = [0 for j in range(n+1)]
ret = 0
for row in matrix:
for j in range(n):
heights[j] = 0 if row[j] == "0" else heights[j] + 1
ret = max(ret, self.largestRectangleArea(heights, n))

return ret
------ 本文结束------
0%