Участник:S1td1kov/MaximalRectangle

Материал из DISCOPAL
Перейти к: навигация, поиск

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

//follow my github https://github.com/RusS1103/Leetcode
 
const int ZERO = [](){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    return 0;
}();
 
class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int max_area = 0, i = 0, size = height.size();
        for (stack<int> stk; i<size || !stk.empty(); )
            if (stk.empty() || (i != size && height[stk.top()] <= height[i])) stk.push(i++);
            else {
                int tp = stk.top(); stk.pop();
                max_area = max(max_area, height[tp] * (stk.empty() ? i : i-stk.top()-1));
            }
        return max_area;
    }
    int maximalRectangle(vector<vector<char> > &matrix) {
        if (matrix.empty()) return 0;
        int max_area = 0;
        vector<int> height(matrix[0].size(), 0);
        for (size_t i=0; i<matrix.size(); ++i) {
            for (size_t j=0; j<matrix[0].size(); ++j)
                if (matrix[i][j] == '0') height[j] = 0;
                else ++height[j];
            max_area = max(max_area, largestRectangleArea(height));
        }
        return max_area;
    }
};