84-柱形图中最大矩形

LeetCode 84. Largest Rectangle in Histogram

LeetCode-84

Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

method: 单调栈

计算区间中元素个数

• 左闭右闭[i, j]: i-j+1
• 左闭右开[i, j): j-i
• 左开右开(i, j): j-i-1

维护一个从栈底到栈顶单调递增的栈，如果heights[i]比栈顶元素大就入栈，小就栈顶元素出栈。
计算面积的逻辑，高度就是栈顶元素的高度，宽度的确定：

• 如果栈是空的，说明从下标0开始的所有元素都比topIdx大，而heights[i]比他小，所以他能到达的宽度区间就是[0, i)，即为i

• 如果栈非空，top肯定比刚弹出的topIdx小，并且heights[i]也比topIdx小，所以他能到达的宽度区间是(st.top, i)，即为i-st.top-1

栈非空有两种情况，为什么不是i-topIdx，因为现在的top和topIdx之间可能还有值，只不过已经弹出了

int largestRectangleArea(vector<int>& heights) {
    stack<int> st;
    int res = 0;
    heights.push_back(0);
    for (int i = 0; i < heights.size(); i++) {
        while (!st.empty() && heights[i] < heights[st.top()]) {
            int topIdx = st.top();
            st.pop();
            int h = heights[topIdx];
            int w = st.empty() ? i : i - st.top() - 1;
            res = max(res, h * w);
        }
        st.push(i);
    }
    return res;
}

---

LeetCode 85. Maximal Rectangle

Given a rows x cols binary matrix filled with 0‘s and 1‘s, find the largest rectangle containing only 1‘s and return its area.

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.

method

84-柱形图中最大矩形的进阶版

对于每一行，都是一个柱形图，都可以求一个最大矩形

• 先算出每一行的柱形图的高度
• 遍历每一行，都用单调栈算一个最大矩形问题

int maximalRectangle(vector<vector<char>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    vector<vector<int>> height(m, vector<int>(n + 1, 0));   // 注意这里是n+1
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == '1') {
                height[i][j] = (i == 0 ? 0 : height[i - 1][j]) + 1;
            }
        }
    }
    int res = 0;
    for (int i = 0; i < m; i++) {
        stack<int> st;
        for (int j = 0; j <= n; j++) {  // 末尾要补一个0
            while (!st.empty() && height[i][j] < height[i][st.top()]) {
                int topIdx = st.top();
                st.pop();
                int h = height[i][topIdx];
                int w = st.empty() ? j : j - st.top() - 1;
                res = max(res, h * w);
            }
            st.push(j);
        }
    }
    return res;
}