算法leetcode｜85. 最大矩形（rust重拳出击）

---

---

85. 最大矩形：

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

样例 1：

输入：
	
	matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
	
输出：
	
	6
	
解释：
	
	最大矩形如上图所示。
1
2
3
4
5
6
7
8
9
10
11

样例 2：

输入：
	
	matrix = []
	
输出：
	
	0
1
2
3
4
5
6
7

样例 3：

输入：
	
	matrix = [["0"]]
	
输出：
	
	0
1
2
3
4
5
6
7

样例 4：

输入：
	
	matrix = [["1"]]
	
输出：
	
	1
1
2
3
4
5
6
7

样例 5：

输入：
	
	matrix = [["0","0"]]
	
输出：
	
	0
1
2
3
4
5
6
7

提示：

• rows == matrix.length
• cols == matrix[0].length
• 1 <= row, cols <= 200
• matrix[i][j] 为 ‘0’ 或 ‘1’

---

分析：

• 面对这道算法题目，二当家的再次陷入了沉思。
• 要不是刚做过 84. 柱状图中最大的矩形 这道题，差点就被唬住，就去暴力破解了。
• 可以从上到下的遍历，把矩阵按照柱状图处理，纵向从下往上计算高度，遇到0停止。
• 处理柱状图最直接的想法是双循环，遍历每个柱子，查找左边第一个低于自己的柱子，和右边第一个低于自己的柱子，这样就能算出当前柱子这个高度最大的宽度，有搞头，很明显会很慢，还有没有更好的办法呢。
• 找到每个柱子的左右边界（第一个低于自己的柱子）是关键，有没有办法降低查找的复杂度呢？
• 要是能一次遍历就把左右边界找到就好了，祭出神器单调栈，如果栈为空就入栈（这里可以使用技巧，让处理逻辑统一），否则判断下一个柱子如果高于栈顶或者和栈顶一样高也直接入栈，如果低于栈顶就出栈，因为当前这个柱子就是栈顶元素的右边界，重复这个过程，就可以在一次遍历的过程中就找到左右边界。
• 特别要注意遍历过程中栈为空，和遍历完所有柱子但是栈不为空的情况。

---

题解：

rust：

impl Solution {
    pub fn maximal_rectangle(matrix: Vec<Vec<char>>) -> i32 {
        let mut ans = 0;

        let (rows, cols) = (matrix.len(), matrix[0].len());
        let mut heights = vec![0; cols];
        let mut stack = vec![-1];
        (0..rows).for_each(|i| {
            (0..cols).for_each(|j| {
                // 矩阵转换为柱状图（滚动数组）
                if matrix[i][j] == '1' {
                    heights[j] += 1;
                } else {
                    heights[j] = 0;
                }

                while stack.len() > 1 && heights[*stack.last().unwrap() as usize] > heights[j] {
                    // 栈中比当前位置高的那些待确定右边界的下标都可以确定右边界了

                    ans = ans.max(heights[stack.pop().unwrap() as usize] * (j as i32 - 1 - stack.last().unwrap()));
                }
                // 入栈，等到能够确定右边界时处理
                stack.push(j as i32);
            });

            while stack.len() > 1 {
                // 栈中剩余的都是右边没有更低的

                ans = ans.max(heights[stack.pop().unwrap() as usize] * (cols as i32 - 1 - stack.last().unwrap()));
            }
        });

        return ans;
    }
}
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

---

go：

func maximalRectangle(matrix [][]byte) int {
    max := func(x, y int) int {
		if x > y {
			return x
		}
		return y
	}

	ans := 0

	rows, cols := len(matrix), len(matrix[0])
	heights := make([]int, cols)
	stack := []int{-1}
	for i := 0; i < rows; i++ {
		for j := 0; j < cols; j++ {
			// 矩阵转换为柱状图（滚动数组）
			if matrix[i][j] == '1' {
				heights[j]++
			} else {
				heights[j] = 0
			}

			for len(stack) > 1 && heights[stack[len(stack)-1]] > heights[j] {
				// 栈中比当前位置高的那些待确定右边界的下标都可以确定右边界了

				ans = max(ans, heights[stack[len(stack)-1]]*(j-1-stack[len(stack)-2]))
				// 出栈
				stack = stack[:len(stack)-1]
			}
			// 入栈，等到能够确定右边界时处理
			stack = append(stack, j)
		}

		for len(stack) > 1 {
			// 栈中剩余的都是右边没有更低的

			ans = max(ans, heights[stack[len(stack)-1]]*(cols-1-stack[len(stack)-2]))
			// 出栈
			stack = stack[:len(stack)-1]
		}
	}

	return ans
}
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
39
40
41
42
43
44

---

c++：

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int ans = 0;

        const int rows = matrix.size();
        const int cols = matrix[0].size();
        int heights[cols];
        memset(heights, 0, sizeof(int) * cols);
        stack<int> s;
        s.push(-1);
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                // 矩阵转换为柱状图（滚动数组）
                if (matrix[i][j] == '1') {
                    heights[j] += 1;
                } else {
                    heights[j] = 0;
                }

                while (s.size() > 1 && heights[s.top()] > heights[j]) {
                    // 栈中比当前位置高的那些待确定右边界的下标都可以确定右边界了

                    int height = heights[s.top()];
                    s.pop();
                    ans = max(ans, height * (j - 1 - s.top()));
                }
                // 入栈，等到能够确定右边界时处理
                s.push(j);
            }

            while (s.size() > 1) {
                // 栈中剩余的都是右边没有更低的

                int height = heights[s.top()];
                s.pop();
                ans = max(ans, height * (cols - 1 - s.top()));
            }
        }

        return ans;
    }
};
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
39
40
41
42
43

---

python：

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        ans = 0

        rows = len(matrix)
        cols = len(matrix[0])
        heights = [0] * cols
        stack = [-1]
        for i in range(rows):
            for j in range(cols):
                # 矩阵转换为柱状图（滚动数组）
                if matrix[i][j] == '1':
                    heights[j] += 1
                else:
                    heights[j] = 0

                while len(stack) > 1 and heights[stack[-1]] > heights[j]:
                    # 比当前位置高的那些待确定右边界的下标都可以确定右边界了
                    ans = max(ans, heights[stack.pop()] * (j - 1 - stack[-1]))
                # 入栈，等到能够确定右边界时处理
                stack.append(j)
            while len(stack) > 1:
                # 栈中剩余的都是右边没有更低的
                ans = max(ans, heights[stack.pop()] * (cols - 1 - stack[-1]))

        return ans

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

---

java：

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int ans = 0;

        final int      rows    = matrix.length;
        final int      cols    = matrix[0].length;
        final int[]    heights = new int[cols];
        Deque<Integer> stack   = new ArrayDeque<>();
        stack.push(-1);
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                // 矩阵转换为柱状图（滚动数组）
                if (matrix[i][j] == '1') {
                    heights[j] += 1;
                } else {
                    heights[j] = 0;
                }

                while (stack.size() > 1 && heights[stack.peek()] > heights[j]) {
                    // 栈中比当前位置高的那些待确定右边界的下标都可以确定右边界了

                    ans = Math.max(ans, heights[stack.pop()] * (j - 1 - stack.peek()));
                }
                // 入栈，等到能够确定右边界时处理
                stack.push(j);
            }

            while (stack.size() > 1) {
                // 栈中剩余的都是右边没有更低的

                ans = Math.max(ans, heights[stack.pop()] * (cols - 1 - stack.peek()));
            }
        }

        return ans;
    }
}
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

---

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~

---