leetcode_maximal_rectangle

发表于

难度：Medium

此题是柱形图最大长方形面积的扩展，在每一行，向上进行扩展，’1’为阴影。

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

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.size()==0 || matrix[0].size()==0) return 0;
        vector<int> heights(matrix[0].size()+1,0);
        int res=0;
        for(int i = 0; i < matrix.size(); i++)
        {
            matrix[i].push_back('0');
            stack<int> s;
            for(int j = 0; j < matrix[i].size(); j++)
            {
                if(matrix[i][j] == '1')
                {
                    heights[j]++;
                }
                else
                    heights[j] = 0;
                while(!s.empty() && heights[s.top()] >= heights[j])
                {
                    int cur_j = s.top();
                    s.pop();
                    int area = heights[cur_j]*(s.empty()?j:(j-s.top()-1));
                    res = max(res,area);
                }
                s.push(j);
            }
        }
        
        return res;
    }
};