85. 最大矩形：
給定一個(gè)僅包含 0 和 1 、大小為 rows x cols 的二維二進(jìn)制矩陣，找出只包含 1 的最大矩形，并返回其面積。
樣例 1：
文章來源：http://www.zghlxwxcb.cn/news/detail-714075.html
輸入：
matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
輸出：
6
解釋：
最大矩形如上圖所示。
樣例 2：
輸入：
matrix = []
輸出：
0
樣例 3：
輸入：
matrix = [["0"]]
輸出：
0
樣例 4：
輸入：
matrix = [["1"]]
輸出：
1
樣例 5：
輸入：
matrix = [["0","0"]]
輸出：
0
提示：
- rows == matrix.length
- cols == matrix[0].length
- 1 <= row, cols <= 200
- matrix[i][j] 為 ‘0’ 或 ‘1’
分析：
- 面對這道算法題目，二當(dāng)家的再次陷入了沉思。
- 要不是剛做過 84. 柱狀圖中最大的矩形 這道題，差點(diǎn)就被唬住，就去暴力破解了。
- 可以從上到下的遍歷，把矩陣按照柱狀圖處理，縱向從下往上計(jì)算高度，遇到0停止。
- 處理柱狀圖最直接的想法是雙循環(huán)，遍歷每個(gè)柱子，查找左邊第一個(gè)低于自己的柱子，和右邊第一個(gè)低于自己的柱子，這樣就能算出當(dāng)前柱子這個(gè)高度最大的寬度，有搞頭，很明顯會(huì)很慢，還有沒有更好的辦法呢。
- 找到每個(gè)柱子的左右邊界（第一個(gè)低于自己的柱子）是關(guān)鍵，有沒有辦法降低查找的復(fù)雜度呢？
- 要是能一次遍歷就把左右邊界找到就好了，祭出神器單調(diào)棧，如果棧為空就入棧（這里可以使用技巧，讓處理邏輯統(tǒng)一），否則判斷下一個(gè)柱子如果高于棧頂或者和棧頂一樣高也直接入棧，如果低于棧頂就出棧，因?yàn)楫?dāng)前這個(gè)柱子就是棧頂元素的右邊界，重復(fù)這個(gè)過程，就可以在一次遍歷的過程中就找到左右邊界。
- 特別要注意遍歷過程中棧為空，和遍歷完所有柱子但是棧不為空的情況。
題解：
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| {
// 矩陣轉(zhuǎn)換為柱狀圖（滾動(dòng)數(shù)組）
if matrix[i][j] == '1' {
heights[j] += 1;
} else {
heights[j] = 0;
}
while stack.len() > 1 && heights[*stack.last().unwrap() as usize] > heights[j] {
// 棧中比當(dāng)前位置高的那些待確定右邊界的下標(biāo)都可以確定右邊界了
ans = ans.max(heights[stack.pop().unwrap() as usize] * (j as i32 - 1 - stack.last().unwrap()));
}
// 入棧，等到能夠確定右邊界時(shí)處理
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;
}
}
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++ {
// 矩陣轉(zhuǎn)換為柱狀圖（滾動(dòng)數(shù)組）
if matrix[i][j] == '1' {
heights[j]++
} else {
heights[j] = 0
}
for len(stack) > 1 && heights[stack[len(stack)-1]] > heights[j] {
// 棧中比當(dāng)前位置高的那些待確定右邊界的下標(biāo)都可以確定右邊界了
ans = max(ans, heights[stack[len(stack)-1]]*(j-1-stack[len(stack)-2]))
// 出棧
stack = stack[:len(stack)-1]
}
// 入棧，等到能夠確定右邊界時(shí)處理
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
}
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) {
// 矩陣轉(zhuǎn)換為柱狀圖（滾動(dòng)數(shù)組）
if (matrix[i][j] == '1') {
heights[j] += 1;
} else {
heights[j] = 0;
}
while (s.size() > 1 && heights[s.top()] > heights[j]) {
// 棧中比當(dāng)前位置高的那些待確定右邊界的下標(biāo)都可以確定右邊界了
int height = heights[s.top()];
s.pop();
ans = max(ans, height * (j - 1 - s.top()));
}
// 入棧，等到能夠確定右邊界時(shí)處理
s.push(j);
}
while (s.size() > 1) {
// 棧中剩余的都是右邊沒有更低的
int height = heights[s.top()];
s.pop();
ans = max(ans, height * (cols - 1 - s.top()));
}
}
return ans;
}
};
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):
# 矩陣轉(zhuǎn)換為柱狀圖（滾動(dòng)數(shù)組）
if matrix[i][j] == '1':
heights[j] += 1
else:
heights[j] = 0
while len(stack) > 1 and heights[stack[-1]] > heights[j]:
# 比當(dāng)前位置高的那些待確定右邊界的下標(biāo)都可以確定右邊界了
ans = max(ans, heights[stack.pop()] * (j - 1 - stack[-1]))
# 入棧，等到能夠確定右邊界時(shí)處理
stack.append(j)
while len(stack) > 1:
# 棧中剩余的都是右邊沒有更低的
ans = max(ans, heights[stack.pop()] * (cols - 1 - stack[-1]))
return ans
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) {
// 矩陣轉(zhuǎn)換為柱狀圖（滾動(dòng)數(shù)組）
if (matrix[i][j] == '1') {
heights[j] += 1;
} else {
heights[j] = 0;
}
while (stack.size() > 1 && heights[stack.peek()] > heights[j]) {
// 棧中比當(dāng)前位置高的那些待確定右邊界的下標(biāo)都可以確定右邊界了
ans = Math.max(ans, heights[stack.pop()] * (j - 1 - stack.peek()));
}
// 入棧，等到能夠確定右邊界時(shí)處理
stack.push(j);
}
while (stack.size() > 1) {
// 棧中剩余的都是右邊沒有更低的
ans = Math.max(ans, heights[stack.pop()] * (cols - 1 - stack.peek()));
}
}
return ans;
}
}
非常感謝你閱讀本文~
歡迎【點(diǎn)贊】【收藏】【評論】三連走一波~
放棄不難，但堅(jiān)持一定很酷~
希望我們大家都能每天進(jìn)步一點(diǎn)點(diǎn)~
本文由 二當(dāng)家的白帽子：https://le-yi.blog.csdn.net/ 博客原創(chuàng)~文章來源地址http://www.zghlxwxcb.cn/news/detail-714075.html
到了這里，關(guān)于算法leetcode｜85. 最大矩形（rust重拳出擊）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
