最大矩形（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
示例 3：
输入：matrix = [["0"]]
输出：0
示例 4：
输入：matrix = [["1"]]
输出：1
示例 5：
输入：matrix = [["0","0"]]
输出：0
这题要结合leetcode84题来看，84题是给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。
本题我们可以扩展下，先求出矩阵中每一个“1”左边有多少个“1”，这个数字就是84题中“柱子的高度”，然后遍历矩阵的每一列，求出该列为底的情况下左边能勾勒出的矩阵的最大面积。
在84题中，我们可以思路可以类比接雨水那一题，核心思路就是找到每一个柱子两边的第一个比其矮的柱子，两者下标之差乘以该柱子的高度就是当前能构成的最大面积。
了解到基本思路后，我们在这里使用单调栈，保证栈里面的元素都是单调增加的，这样就可以在新增元素的时候，如果小于当前的栈顶，那么当前栈顶右边第一个比其小的元素就是该新增元素，此时弹出栈顶，栈中下一个元素接着比，直到找到第一个比新增元素小的，那么该新增元素的左边第一个比它小的就是该元素。我们用两个数组来存左边和右边的，左边第一个小的元素全部初始化为0，右边第一个小的全部初始化为最后一个元素。
最后算面积的时候就是遍历，每个用右边减去左边乘以高度就得到面积。
下面直接上代码：
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
// class Solution
// {
// public:
// int maximalRectangle(vector<vector<char> > &matrix)
// {
// int m = matrix.size();
// if (m == 0)
// {
// return 0;
// }
// int n = matrix[0].size();
// vector<vector<int> > left(m, vector<int>(n, 0));
// for (int i = 0; i < m; i++)
// {
// for (int j = 0; j < n; j++)
// {
// if (matrix[i][j] == '1')
// left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
// }
// }
// int res = 0;
// for (int j = 0; j < n; j++)
// {
// vector<int> up(m, 0), down(m, 0);
// stack<int> stk;
// for (int i = 0; i < m; i++)
// {
// while (!stk.empty() && left[stk.top()][j] >= left[i][j])
// {
// stk.pop();
// }
// up[i] = stk.empty() ? -1 : stk.top();
// stk.push(i);
// }
// stk = stack<int>();
// for (int i = m - 1; i >= 0; i--)
// {
// while (!stk.empty() && left[stk.top()][j] >= left[i][j])
// {
// stk.pop();
// }
// down[i] = stk.empty() ? m : stk.top();
// stk.push(i);
// }
// for (int i = 0; i < m; i++)
// {
// int height = down[i] - up[i] - 1;
// int area = height * left[i][j];
// res = max(res, area);
// }
// }
// return res;
// }
// };
// class Solution
// {
// public:
// int maximalRectangle(vector<vector<char>> &matrix)
// {
// if (matrix.size() == 0 || matrix[0].size() == 0)
// {
// return 0;
// }
// int len = matrix[0].size() + 2, n = matrix.size(), rs = 0;
// int high[len];
// memset(high, 0, sizeof(high));
// for (int row = 0; row < n; row++)
// {
// for (int i = 1; i < len - 1; i++)
// {
// if (matrix[row][i - 1] == '0')
// {
// high[i] = 0;
// }
// else
// {
// high[i] = high[i] + 1;
// }
// }
// vector<int> hset;
// hset.push_back(0);
// for (int i = 1; i < len; i++)
// {
// while (high[hset.back()] > high[i])
// {
// rs = max(rs, high[hset.back()] * (i - 1 - hset[hset.size() - 2]));
// hset.pop_back();
// }
// hset.push_back(i);
// }
// }
// return rs;
// }
// };
class Solution
{
public:
int maximalRectangle(vector<vector<char>> &matrix)
{
if (matrix.empty()) return 0;
int m = matrix.size(), n = matrix[0].size();
int ans = 0;
vector<vector<int> > left(m, vector<int>(n, 0));
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (matrix[i][j] == '1')
left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
}
}
for (int j = 0; j < n; ++j)
{
stack<int> stk;
vector<int> up(m, 0), down(m, m);
for (int i = 0; i < m; ++i)
{
while (!stk.empty() && left[stk.top()][j] > left[i][j])
{
down[stk.top()] = i;
stk.pop();
}
up[i] = stk.empty() ? -1 : stk.top();
stk.push(i);
}
for (int i = 0; i < m; i++)
{
ans = max(ans, left[i][j] * (down[i] - up[i] - 1));
}
}
return ans;
}
};