首页 > itarticle > maximal rectangle

maximal rectangle

admin 1月 18, 2021 0

I found two interesting algorithm problems.

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.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
class :
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        heights.append(0)
        stack = []
        i = 0
        result = 0
        while i<len(heights):
            if not stack or heights[stack[-1]]<heights[i]:
                stack.append(i)
                i+=1
            else:
                num = stack.pop(-1)
                result = max(result,heights[num]*(i-stack[-1]-1 if stack else i))
        return result

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

Idea

At first, I was seeking for Dynamic Programing solutions. But when related this problem to the former Largest Rectangle in Histogram problem, There is a clean solution.

You just need to run a for loop to extend the aforementioned one-dimensional Histigram to a 2-dimensional problem.

Code

So, here is the 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
33
34
35
36
37
38
 
class :
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if len(matrix)==0:
            return 0
        
        row = len(matrix)
        column = len(matrix[0])
        temp = [0 for i in range(column)]
        i = 0
        result = 0
        while i<row:
            for j in range(column):
                temp[j] = (0 if matrix[i][j]=='0' else temp[j]+1)
            result = max(result, self.largestRectangleArea(temp))
            i+=1
        return result
                    
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        heights.append(0)
        stack = []
        i = 0
        result = 0
        while i<len(heights):
            if not stack or heights[stack[-1]]<heights[i]:
                stack.append(i)
                i+=1
            else:
                num = stack.pop(-1)
                result = max(result,heights[num]*(i-stack[-1]-1 if stack else i))
        return result
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能