首页 > 其他 > 详细

85. Maximal Rectangle

时间:2018-05-20 10:10:18      阅读:217      评论:0      收藏:0      [点我收藏+]

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

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<int> v(n, 0);
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0)
                    v[j] = 0;
                else
                    v[j]++;
            }
            res = max(res, helper(v));
        }
        return res;
    }
    int helper(const vector<int>& v) {
        stack<int> s;
        int res = 0;
        for (int i = 0; i <= v.size(); i++) {
            int cur = i == v.size() ? 0 : v[i];
            while (!s.empty() && cur < v[s.top()]) {
                int idx = s.top();
                s.pop();
                int w = s.empty() ? i : i - s.top() - 1;
                res = max(res, w * v[idx]);
            }
            s.push(i);
        }
        return res;
    }
};

 

85. Maximal Rectangle

原文:https://www.cnblogs.com/JTechRoad/p/9062357.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!