细语呢喃

技术改变生活

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

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.

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

就是上面那一题。

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/

请我喝杯咖啡吧~