首页 > 其他分享 >leetCode. 85. 最大矩形

leetCode. 85. 最大矩形

时间:2024-05-29 13:58:47浏览次数:32  
标签:size matrix int ret st 矩形 leetCode 85

leetCode. 85. 最大矩形


部分参考上一题链接
leetCode.84. 柱状图中最大的矩形


此题思路
在这里插入图片描述


代码

class Solution {
public:
    int largestRectangleArea( vector<int>& h ) {
        int n = h.size();
        vector<int> left( n ), right( n );
        stack<int> st;

        // 求每个矩形的第一个小于左边界的矩形 - 用单调栈
        for ( int i = 0; i < n; ++i ) {
            while ( st.size() && h[st.top()] >= h[i] ) st.pop();
            if ( st.empty() ) left[i] = -1;
            else left[i] = st.top();
            st.push( i );
        }

        // 求每个矩形的第一个小于右边界的矩形 - 用单调栈
        st = stack<int>(); // 清空栈
        for ( int i = n - 1; i >= 0; --i ) {
            while ( st.size() && h[st.top()] >= h[i] ) st.pop();
            if( st.empty() ) right[i] = n;
            else right[i] = st.top();
            st.push( i );
        }

        // 遍历维护 最大值
        int ret = 0;
        for (int i = 0; i < n; ++i) ret = max( ret, (right[i] - left[i] - 1) * h[i] );

        return ret;
    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.size() == 0 || matrix[0].size() == 0) return 0;
        int n = matrix.size(), m = matrix[0].size();// n 行, m 列
        vector<vector<int>> h(n,vector<int>(m));

        for(int i = 0; i < n; i ++) {
            for(int j = 0; j < m; j ++) {
                if(matrix[i][j] == '1') {
                    if(i) h[i][j] = 1 + h[i - 1][j]; 
                    else h[i][j] = 1; 
                } 
            }
        }

        int ret = 0;
        // 把每行的矩形,按照上题的思路进行处理,然后维护最大值就好
        for(int i = 0; i < n; i ++) ret = max(ret, largestRectangleArea(h[i]));

        return ret;
    }
};

标签:size,matrix,int,ret,st,矩形,leetCode,85
From: https://blog.csdn.net/qq_48290779/article/details/139276240

相关文章

  • LeetCode 1329. Sort the Matrix Diagonally
    原题链接在这里:https://leetcode.com/problems/sort-the-matrix-diagonally/description/题目:A matrixdiagonal isadiagonallineofcellsstartingfromsomecellineitherthetopmostroworleftmostcolumnandgoinginthebottom-rightdirectionuntilreachin......
  • (免费领源码)Java/Mysql数据库+00485 个性化音乐推荐系统的设计与实现,计算机毕业设计项
    毕业设计(论文)NodeJS个性化音乐推荐系统学   院:                           专   业:                           年   级:                           姓   名:  ......
  • Leetcode621. 任务调度器
    EverydayaLeetcode题目来源:621.任务调度器类似题目:1953.你可以工作的最大周数解法1:贪心本质上来说,我们需要构造一个尽量短的,相同元素间隔>=(n+1)的序列。用一个数组cnt统计每个任务的次数。设cnt的元素和为s,这是任务总数,也是序列长度的下界。当存在多个......
  • 2-链表-41-两两交换链表中的节点-LeetCode24
    2-链表-41-两两交换链表中的节点-LeetCode24参考:代码随想录LeetCode:题目序号24更多内容欢迎关注我(持续更新中,欢迎Star✨)Github:CodeZeng1998/Java-Developer-Work-Note技术公众号:CodeZeng1998(纯纯技术文)生活公众号:好锅(Lifeismorethancode)CSDN:CodeZeng1998......
  • 在 Cognex VisionPro CogRecordDisplay 中创建交互式矩形区域
    在CognexVisionProCogRecordDisplay中创建交互式矩形区域在图像处理和视觉检测应用中,定义和操作特定区域是至关重要的。本文将演示如何在CognexVisionPro中使用C#创建一个可交互的矩形区域,并启用拖拽和调整大小功能,从而提升图像处理的灵活性和效率。前提条件安......
  • leetcode 3165. 不包含相邻元素的子序列的最大和
    思路题目中不相邻子序列和的最大值是满足加和性质的,考虑使用线段树,这里我用了4颗线段树,sum[o][l][r]中l=0和l=1分别表示当前区间是否选取左端点作为子序列的一部分,r=0和r=1分别表示当前区间是否选取右端点作为子序列的一部分。接下来就是线段树单点更新。1#defineIOstd::i......
  • LeetCode/NowCoder-栈和队列OJ练习
    孜孜不倦:孜孜:勤勉,不懈怠。指工作或学习勤奋不知疲倦。......
  • 「杂题乱刷」P8572
    链接发现这东西就很根号分治。考虑两种情况:\(k\le1000\),这部分直接用前缀和维护然后暴力做,时间复杂度\(O(kq)\)。\(k>1000\),此时\(n\le500\),这部分直接预处理答案,时间复杂度\(O(n^2k)\)。两个时间复杂度均正确,因此可以通过此题。代码:点击查看代码/*Tips......
  • 【LeetCode算法】第88题:合并两个有序数组
    目录一、题目描述二、初次解答三、官方解法四、总结一、题目描述二、初次解答1.思路:首次想到的解法:定义一个m+n长度的辅助数组,从头遍历这两个数组,谁小就放进辅助数组中并且对应往后走,最后使用memcpy函数将辅助数组内容拷贝到nums1中。这种解法容易想到,但是空间复杂......
  • 【LeetCode算法】第83题:删除排序链表中的重复元素
    目录一、题目描述二、初次解答三、官方解法四、总结一、题目描述二、初次解答1.思路:双指针法,只需遍历一遍。使用low指向前面的元素,high用于查找low后面与low不同内容的节点。将具有不同内容的节点链接在low后面,实现重复元素的删除。2.代码:/***Definitionfor......