最大矩形区域面积

从这个问题想到单调栈结构确实有点不容易，我们举例说明：

1. 0 0 1 1 0 1 1
2. 0 0 1 1 1 0 1
3. 0 1 1 1 1 1 0
4. 1 0 0 0 0 1 1

然后将每个元素转化为该元素及上面相连的1的个数和：

1. 0 0 1 1 0 1 1
2. 0 0 2 2 1 0 2
3. 0 1 3 3 2 1 0
4. 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;
    }
};