从这个问题想到单调栈结构
确实有点不容易,我们举例说明:
0 0 1 1 0 1 1
0 0 1 1 1 0 1
0 1 1 1 1 1 0
1 0 0 0 0 1 1
然后将每个元素转化为该元素及上面相连的1的个数和:
0 0 1 1 0 1 1
0 0 2 2 1 0 2
0 1 3 3 2 1 0
1 0 0 0 0 2 1
以第3行为例,转化成柱形图,下图:
是不是很熟悉呢?对的,其实这就是单调栈结构的一个典型应用,以求上面图片中最大矩形面积为例,单调栈的实现如下(建议作为单调栈题目的模版去记忆):
int monotoneStack(vector<int> &vec) { stack<int> st; vec.push_back(0); // ➤ 添加一个0可以在循环的最后一步清空栈 int maxVal = 0; for (int i = 0; i < vec.size(); ++i) { // 这里用单调递增栈 while (!st.empty() && vec[i] < vec[st.top()]) { int height = vec[st.top()]; st.pop(); int left = st.empty() ? -1 : st.top(); int width = i - (left+1); maxVal = max(maxVal, height * width); } st.push(i); } return maxVal; }
完整代码如下:
// // Created by jt on 2020/9/2. // #include <vector> #include <stack> using namespace std; class Solution { public: int maximalRectangle(vector<vector<char> > &matrix) { if (matrix.empty() || matrix[0].empty()) return 0; vector<vector<int> > tmp(matrix.size(), vector<int>(matrix[0].size())); // 第一次遍历:将char型数组转化为int型数组 for (int i = 0; i < matrix.size(); ++i) { for (int j = 0; j < matrix[0].size(); ++j) { tmp[i][j] = matrix[i][j] - '0'; } } // 第二次遍历:转化矩阵 for (int i = 1; i < tmp.size(); ++i) { for (int j = 0; j < tmp[0].size(); ++j) { if (tmp[i][j] == 1) tmp[i][j] = tmp[i - 1][j] + 1; } } // 第三次遍历:单调递增栈求最大矩阵面积 int maxVal = 0; for (int i = 0; i < tmp.size(); ++i) { maxVal = max(maxVal, monotoneStack(tmp[i])); } return maxVal; } private: int monotoneStack(vector<int> &vec) { stack<int> st; vec.push_back(0); // ➤ 添加一个0可以在循环的最后一步清空栈 int maxVal = 0; for (int i = 0; i < vec.size(); ++i) { // 这里用单调递增栈 while (!st.empty() && vec[i] < vec[st.top()]) { int height = vec[st.top()]; st.pop(); int left = st.empty() ? -1 : st.top(); int width = i - (left+1); maxVal = max(maxVal, height * width); } st.push(i); } return maxVal; } };