Maximal Rectangle（C++最大矩形）

素颜马尾好姑娘i 2023-01-17 04:56 214阅读 0赞

解题思路：

（1）每一行单调栈

class Solution {
    public:
        int helper(vector<int>& h) {
            int n=h.size();
            vector<int> left(n),right(n,n);
            
            stack<int> s;
            for(int i=0;i<n;i++) {
                while(!s.empty() && h[s.top()]>=h[i]) {
                    right[s.top()]=i;
                    s.pop();
                }
                left[i]=s.empty()?-1:s.top();
                s.push(i);
            }
            
            int maxsum=0;
            for(int i=0;i<n;i++) {
                maxsum=max(maxsum,(right[i]-left[i]-1)*h[i]);
            }
            return maxsum;
        }
    
    
        int maximalRectangle(vector<vector<char>>& matrix) {
            int m=matrix.size();
            if(m==0) return 0;
            int n=matrix[0].size();
            int maxsum=0;
            vector<int> v(n,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]++;
                }
            maxsum=max(maxsum,helper(v));
            }
            return maxsum;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，214人围观）

还没有评论，来说两句吧...

相关阅读

相关最大矩形

一、前言问题来源LeetCode 85，难度：困难问题链接：[https://leetcode-cn.com/problems/maximal-rectangle/

绝地灬酷狼/ 2023年02月11日 15:30/ 0 赞/ 152 阅读

相关 Maximal Rectangle（C++最大矩形）

解题思路：（1）每一行单调栈 class Solution { public: int helper(vector<int>& h) {

素颜马尾好姑娘i/ 2023年01月17日 04:56/ 0 赞/ 215 阅读

相关 85. 最大矩形

![20210302182037453.png][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly

- 日理万妓/ 2022年11月04日 13:23/ 0 赞/ 171 阅读

相关 leetcode85最大矩形

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

àì夳堔傛蜴生んèń/ 2022年10月06日 08:51/ 0 赞/ 181 阅读

相关 leetcode 85. Maximal Rectangle | 85. 最大矩形（单调栈）

题目 [https://leetcode.com/problems/maximal-rectangle/][https_leetcode.com_problems_max

男娘i/ 2022年09月11日 11:23/ 0 赞/ 81 阅读

相关 Maximal Square（C++最大正方形）

（1）动态规划 class Solution { public: int maximalSquare(vector<vector<cha

不念不忘少年蓝@/ 2022年09月04日 00:49/ 0 赞/ 177 阅读

相关 LeetCode：85. Maximal Rectangle（最大的矩形）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

Bertha 。/ 2022年04月10日 02:26/ 0 赞/ 238 阅读

相关【Leetcode】85. Maximal Rectangle（求最大矩形）（动态规划）

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing

一时失言乱红尘/ 2022年02月23日 09:50/ 0 赞/ 301 阅读

相关 LeetCode : 221. Maximal Square 最大正方形

试题 Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containin

た入场券/ 2021年06月24日 16:11/ 0 赞/ 414 阅读

相关 CCF 最大矩形

一.问题描述　　在横轴上放了n个相邻的矩形，每个矩形的宽度是1，而第i（1 ≤ i ≤ n）个矩形的高度是hi。这n个矩形构成了一个直方图。例如，下图中六个矩形的高度就

分手后的思念是犯贱/ 2021年06月24日 14:36/ 0 赞/ 481 阅读