leetcode/maxrectangle.cpp at master · outman119/leetcode · GitHub

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
70
71
72
73
class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        int m = matrix.size();
        if (m == 0)
        {
            return 0;
        }
        int n = matrix[0].size();
        if (n == 0)
        {
            return 0;
        }
        vector<vector<int>>ss(m, vector<int>(n,0));
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (i == 0)
                {
                    ss[i][j] = (matrix[i][j] == '1') ? 1 : 0;
                }
                else
                {
                    ss[i][j] = (matrix[i][j] == '1') ? (ss[i-1][j]+1) : 0;
                }
            }
        }

        int maxaa = 0;
        for (int i = 0; i < m; i++)
        {
            auto tmp = largestRectangleArea(ss[i]);
            maxaa = max(maxaa, tmp);
        }
        return maxaa;
    }
private:
    int largestRectangleArea(vector<int> &height) {
        int len = height.size();
        if (len == 0)
        {
            return 0;
        }
        int maxaera = 0;
        stack<int>ss;
        int i = 0;
        while (i < len)
        {
            if (ss.empty() || height[ss.top()] < height[i])
            {
                ss.push(i);
                i++;
            }
            else
            {
                int tmp = ss.top();
                ss.pop();
                auto area = height[tmp]*(ss.empty()?i:(i-ss.top()-1));
                maxaera = max(area, maxaera);
            }
        }

        while (!ss.empty())
        {
            int tmp = ss.top();
            ss.pop();
            auto area = height[tmp] * (ss.empty() ? i : (i - ss.top() - 1));
            maxaera = max(area, maxaera);
        }
        return maxaera;
    }
};