leetcode.85. 最大矩形

最大矩形

问题描述

---

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

示例:

输入:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
输出: 6

---

动态规划

思路分析

---

heights[i][j]代表[i，j]的高度
heights[i][j] = matrix[i][j]=='1'? heights[i-1][j] + 1:0

dp[i][j][k] 代表以[i,j]为右下角，高度为k可以组成的面积
dp[i][j][k] = dp[i][j-1][k] + k  

---

代码实现

源码

栈

思路分析

---

heights[i][j]代表[i，j]的高度
heights[i][j] = matrix[i][j]==’1’? heights[i-1][j] + 1:0

依据height[i]求leetcode.84. 柱状图中最大的矩形

---

代码实现

源码