ARST打卡第349周

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.empty() || matrix[0].empty()) return 0;
        int m = matrix.size(), n = matrix[0].size();
        vector<int> heights(n, 0);
        int maxArea = 0;
        for(int i = 0; i < m; ++i) {
            // 统计本行对应的heights
            for(int j = 0; j < n; ++j) {
                if(matrix[i][j] == '1') 
                    heights[j] += 1;
                else
                    heights[j] = 0;
            }
            // 对heights这一行用单调栈求最大矩形
            maxArea = max(maxArea, largestRectangleArea(heights));
        }
        return maxArea;
    }
private:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> newHeights = heights;
        newHeights.insert(newHeights.begin(), 0);
        newHeights.push_back(0);
        stack<int> st;
        int maxArea = 0;
        for(int i = 0; i < newHeights.size(); ++i) {
            while(!st.empty() && newHeights[i] < newHeights[st.top()]) {
                int h = newHeights[st.top()];
                st.pop();
                int w = i - st.top() - 1;
                maxArea = max(maxArea, h * w);
            }
            st.push(i);
        }
        return maxArea;
    }
};