leetcode-max-rectangle

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/maximal-rectangle/

　　给你一个01字符矩阵，求最大的只含字符1的矩形面积。

题目分析

　　此题可以直接转化成 https://leetcode.com/problems/largest-rectangle-in-histogram ，可以分别把矩形的第0行….第row-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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        vector<int> nums = heights;
        int s = heights.size();
        if(s == 0) {
            return 0;
        }
        int ans = 0;
        vector<int> left(s, 0);
        vector<int> right(s, 0);
        //left
        left[0] = 0;
        for(int i = 1; i < s; i++) {
            int jump = i;
            while (jump > 0 && nums[jump - 1] >= nums[i]) {
                jump = left[jump - 1];
            }
            left[i] = jump;
        }
        //right
        right[s - 1] = s - 1;
        for(int i = s - 2; i >= 0; i--) {
            int jump = i;
            while (jump < s - 1 && nums[jump + 1] >= nums[i]) {
                jump = right[jump + 1];
            }
            right[i] = jump;
        }
        //
        for(int i = 0; i < s; i++) {
            ans = max(ans, (right[i] - left[i] + 1) * nums[i]);
        }
        return ans;
    }
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) {
            return 0;
        }
        vector<vector<int> > h;
        int row = matrix.size();
        int col = matrix[0].size();
        
        vector<int> rh;
        for (int j = 0; j < col; j++) {
            rh.push_back(matrix[0][j] - '0');
        }
        h.push_back(rh);
        int max = largestRectangleArea(rh);
      
        for (int i = 1; i < row; i++) {
            vector<int> rh2;
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == '0') {
                    rh2.push_back(0);
                } else {
                    rh2.push_back(1 + h[i - 1][j] );
                }
            }
            h.push_back(rh2);
            int area = largestRectangleArea(rh2);
            if (area > max) {
                max = area;
            }
        }
        return max;
    }
};

　　复杂度：O(m * n)