昨天关于钉钉被曝CEO凌晨巡查工位的一则消息上了热搜，原因是有人发文称钉钉CEO“无招”在晚上12点至12点半之间，巡查了一趟办公区域，发现工位上没几个人。结果第二天，他把所有部门都批评（臭骂）了一番，质问大家：为什么提前下班？该消息在网上广为流传，目前还不确定真假，我们坐等官方回应。
打开网易新闻 查看更多图片
打开网易新闻 查看更多图片
打开网易新闻 查看更多图片
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第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 解释：最大矩形如上图所示。
示例2：
输入：matrix = [["0"]] 输出：0
rows == matrix.length
cols == matrix[0].length
1 <= row, cols <= 200
matrix[i][j] 为 '0' 或 '1'
问题分析
这题说的是计算只包含 1 的最大矩形，我们完全可以参照昨天那题的解题思路，把这题转化一下，就可以使用单调栈按照昨天那题的解题思路来解了。
怎么转化呢？我们一行一行的计算，每一行上面有多少个 1 ，就相当于柱子的高度是多少，比如在示例一中，我们计算第 3 行的时候，那么第 3 行的图像就如下图右边所示：
打开网易新闻 查看更多图片
剩下的我们就可以通过昨天那道题来计算，不过和昨天那题不同的是，这题我们需要统计每一行中柱子的高度。
JAVA：
public int maximalRectangle(char[][] matrix) { // n 是矩阵的宽，ans 记录的是最大矩形面积。 int n = matrix[0].length, ans = 0; int[] h = newint[n + 1];// 遍历到第 i 行的时候，每一列的高度。 Stack stk = new Stack<>();// 从栈底到栈顶单调递增 for (char[] chars : matrix) {// 从上到下一行一行的遍历 stk.clear(); stk.push(-1);// 为了方便计算，让栈底元素为 -1 。 for (int i = 0; i <= n; i++) {// 遍历当前行的每一列 if (i < n && chars[i] == '1') h[i]++;// 累加高度 else h[i] = 0;// 重置为 0 while (stk.peek() != -1 && h[i] < h[stk.peek()]) { // h[stk.pop()是矩形的高度，(i - stk.peek() - 1)是矩形的宽度 ans = Math.max(ans, h[stk.pop()] * (i - stk.peek() - 1)); } stk.push(i); } } return ans; }C++：
public: int maximalRectangle(vector
> &matrix) { // n 是矩阵的宽，ans 记录的是最大矩形面积。 int n = matrix[0].size(), ans = 0; vector
h(n + 1, 0);// 遍历到第 i 行的时候，每一列的高度。 for (constvector
&chars: matrix) {// 从上到下一行一行的遍历 stack
stk;// 从栈底到栈顶单调递增 stk.push(-1);// 为了方便计算，让栈底元素为 -1 。 for (int i = 0; i <= n; i++) {// 遍历当前行的每一列 if (i < n && chars[i] == '1') h[i]++;// 累加高度 else h[i] = 0;// 重置为 0 while (stk.top() != -1 && h[i] < h[stk.top()]) { // h[stk.pop()是矩形的高度，注意这个时候栈顶元素已经出栈了， // (i - stk.peek() - 1)是矩形的宽度 int height = h[stk.top()]; stk.pop(); ans = max(ans, height * (i - stk.top() - 1)); } stk.push(i); } } return ans; }
笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解900多题，对算法题有自己独特的解题思路和解题技巧。