<menu id="2icg2"><tt id="2icg2"></tt></menu>
  • <menu id="2icg2"><tt id="2icg2"></tt></menu><menu id="2icg2"></menu>
  • <nav id="2icg2"></nav>
  • <input id="2icg2"><u id="2icg2"></u></input>
  • <input id="2icg2"><u id="2icg2"></u></input>
  • leetcode-85-最大矩形

    题目描述:

    方法一:动态规划+使用柱状图的优化暴力方法 O(N*2M) O(NM) N为行数

    class Solution:
        def maximalRectangle(self, matrix: List[List[str]]) -> int:
            maxarea = 0
    
            dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
            for i in range(len(matrix)):
                for j in range(len(matrix[0])):
                    if matrix[i][j] == 0: continue
    
                    # compute the maximum width and update dp with it
                    width = dp[i][j] = dp[i][j-1] + 1 if j else 1
    
                    # compute the maximum area rectangle with a lower right corner at [i, j]
                    for k in range(i, -1, -1):
                        width = min(width, dp[k][j])
                        maxarea = max(maxarea, width * (i-k+1))
            return maxarea

    方法二:栈 参考84题 O(NM) O(M)

    class Solution:
        def maximalRectangle(self, matrix: List[List[str]]) -> int:
            if not matrix: return 0
            maxarea = 0
            dp = [0 for _ in range(len(matrix[0]))]
            for i in range(len(matrix)):
                for j in range(len(matrix[0])):
                    dp[j] = dp[j] + 1 if matrix[i][j] == "1" else 0
                maxarea = max(maxarea,self.largestRectangleArea(dp))
            return maxarea
    
        def largestRectangleArea(self, heights: List[int]) -> int:
            stack = [0]
            heights = [0] + heights + [0]
            res = 0
            for i in range(len(heights)):
                while heights[stack[-1]] > heights[i]:
                    tmp = stack.pop()
                    res = max(res, (i - stack[-1] - 1) * heights[tmp])
                stack.append(i)
            return res

    方法三:动态规划  O(NM)

    class Solution:
        def maximalRectangle(self, matrix: List[List[str]]) -> int:
            if not matrix or not matrix[0]: return 0
            row = len(matrix)
            col = len(matrix[0])
            left_j = [-1] * col
            right_j = [col] * col
            height_j = [0] * col
            res = 0
            for i in range(row):
                cur_left = -1
                cur_right = col
    
                for j in range(col):
                    if matrix[i][j] == "1":
                        height_j[j] += 1
                    else:
                        height_j[j] = 0
    
                for j in range(col):
                    if matrix[i][j] == "1":
                        left_j[j] = max(left_j[j], cur_left)
                    else:
                        left_j[j] = -1
                        cur_left = j
    
                for j in range(col - 1, -1, -1):
                    if matrix[i][j] == "1":
                        right_j[j] = min(right_j[j], cur_right)
                    else:
                        right_j[j] = col
                        cur_right = j
                for j in range(col):
                    res = max(res, (right_j[j] - left_j[j] - 1) * height_j[j])
            return res
    相关文章
    相关标签/搜索
    管家婆四肖精选期期准 姚安县| 鄱阳县| 东阿县| 天水市| 都匀市| 平阳县| 元氏县| 罗定市| 阿拉善右旗| 廊坊市| 靖宇县| 剑阁县| 泾阳县| 苏尼特左旗| 东源县| 夹江县| 垦利县| 榆林市| 福清市| 香港| 阜平县| 安丘市| 三原县| 营口市| 大同县| 溧水县| 华亭县| 合山市| 安仁县| 龙江县| 泌阳县| 当涂县| 三门县| 会同县| 宣恩县| 鸡泽县| 称多县| 石渠县| 塔城市| 色达县| 兴城市| 广水市| 耒阳市| 望都县| 天津市| 石渠县| 清远市| 木兰县| 两当县| 灌阳县| 康定县| 新宾| 江永县| 汕尾市| 五河县| 南皮县| 澄城县| 泾阳县| 晴隆县| 乌拉特后旗| 清徐县| 乡城县| 石狮市| 琼结县| 绥中县| 古丈县| 镇巴县| 隆德县| 洛隆县| 巴塘县| 绵阳市| 沁阳市| 临安市| 通化市| 镇原县| 高密市| 临邑县| 米林县| 福鼎市| 永川市| 贡山| 闽清县| 佛山市| 获嘉县| 万安县| 黄冈市| 新昌县| 阿拉善右旗| 平和县| 来安县| 九龙坡区| 拉萨市| 虹口区| 紫金县| 大姚县| 台北县| 定襄县| 灵石县| 临洮县| 汉源县| 庐江县| 高清| 饶平县| 凉城县| 安阳市| 西贡区| 三门峡市| 翁源县| 广南县| 石嘴山市| 迭部县| 杭锦后旗| 且末县| 申扎县| 封开县| 茌平县| 广宗县| 若尔盖县| 鄂伦春自治旗| 化隆| 邹城市| 平湖市| 盐边县| 法库县| 榆林市| 普兰店市| 西乌珠穆沁旗| 清水河县| 林芝县| 崇州市| 湘潭市| 菏泽市| 武城县| 葫芦岛市| 乐昌市| 峡江县| 旅游| 托里县| 密云县| 临桂县| 元氏县| 香河县| 临潭县| 永仁县| 荆门市| 东源县| 卢湾区| 镇坪县| 日喀则市| 昌黎县| 成武县| 乳源| 瓮安县| 时尚| 勐海县| 车致| 彝良县| 湟中县| 曲麻莱县| 玉溪市| 华蓥市| 会理县| 汉川市| 太仆寺旗| 武冈市| 和龙市| 萨嘎县| 依兰县| 兴仁县| 阳曲县| 龙泉市| 弥渡县| 沧源| 营山县| 大连市| 富阳市| 鸡西市| 林西县| 泸西县| 鹰潭市| 井陉县| 六盘水市| 延庆县| 台州市| 罗城| 马龙县| 定兴县| 昂仁县| 卫辉市| 四会市| 北碚区| 景泰县| 博湖县| 什邡市| 龙井市| 大石桥市| 万年县| 岫岩| 河津市| 虞城县| 涟水县| 瑞昌市| 镇宁| 黔江区| 惠东县| 临沧市| 雅安市| 连平县| 敦煌市| 尼勒克县| 民权县| 手机| 清水河县| 会昌县| 元阳县| 句容市| 小金县| 嘉义县| 高平市| 高平市| 偏关县| 寻乌县| 秭归县| 绥棱县| 宁武县| 云林县| 米脂县| 四会市| 池州市| 任丘市| 青河县| 西华县| 襄汾县| 金华市| 溆浦县| 略阳县| 福贡县| 宁夏| 遂宁市| 梅州市| 肇庆市| 南岸区| 桃江县| 宁阳县| 隆尧县| 芒康县| 庆云县| 东乌| 延边| 合作市| 滦南县| 常州市| 永德县| 秭归县| 儋州市| 高要市| 理塘县| 柳州市| 襄城县| 诏安县| 墨玉县| 马关县| 上饶县| 富平县| 长葛市| 廊坊市| 湖南省| 绥德县| 凤城市| 铅山县| 平度市| 盐津县| 洛浦县| 长武县| 铜梁县| 广灵县| 昌都县| 泸定县| 马尔康县| 满城县| 西安市| 卓资县| 荆州市| 黔西| 东乡| 张家口市| 清新县| 蓝山县| 宝鸡市| 开封市| 图们市| 塘沽区| 囊谦县| 冕宁县| 绥滨县| 若羌县| 夏津县| 平陆县| 惠来县| 张北县| 沂水县| 达州市| 额敏县| 静海县| 灵石县| 高淳县| 孟村| 富阳市| 大厂| 明溪县| 台中县| 桂阳县| 大石桥市| 白水县| 临海市| 米易县| 安徽省| 定西市| 开原市| 瑞安市| 普宁市| 高陵县| 米林县| 峨边| 舒城县| 石嘴山市| 威海市| 木里| 泽州县| 桑日县| 望江县| 彭水| 墨玉县| 潞城市| 瑞金市| 凭祥市| 社旗县| 桑植县| 广昌县| 太康县| 大邑县| 博白县| 六安市| 华安县| 亚东县| 陆丰市| 古田县| 镇巴县| 陈巴尔虎旗| 湘西| 玉门市| 通化市| 阿城市| 都昌县| 桓台县| 鄄城县| 阿巴嘎旗| 定结县| 光山县| 湖南省| 扎鲁特旗| 同心县| 衢州市| 榕江县| 乾安县| 西昌市| 衡东县| 泸州市| 镇远县| 陆良县| 兰州市| 邢台市| 巴楚县| 兴仁县| 阳江市| 聊城市| 柳河县| 晋州市| 凤庆县| 赣州市| 汽车| 沁水县| 监利县| 蒲江县| 永川市| 永平县| 吴桥县| 喀什市| 景泰县| 康定县| 黄石市| 潜江市| 扬州市| 开鲁县| 邯郸市| 施甸县| 宁安市| 林周县| 乡宁县| 咸宁市| 合川市| 新丰县| 灵台县| 阳原县| 肥乡县| 法库县| 邯郸县| 和政县| 恩平市| 临沭县| 龙井市| 固阳县| 白玉县| 温州市| 图片| 二连浩特市| 延安市| 四平市| 西峡县| 湛江市| 江达县| 中江县| 梅州市| 丹寨县| 兴安县| 蛟河市| 栾川县| 酉阳| 万全县| 两当县| 阳曲县| 揭东县| 两当县| 方山县| 张家港市| 高密市| 正安县| 五指山市| 景洪市| 易门县| 合川市| 仪征市| 彩票| 资溪县| 本溪| 汝州市| 托克逊县| 建阳市| 荔波县| 漳州市| 景洪市| 格尔木市| 濮阳市| 和平县| 高安市| 获嘉县| 靖西县| 祁阳县| 昭通市| 红安县| 诏安县| 明溪县| 中超| 新宁县| 涞水县| 凤冈县| 怀远县| 永兴县| 井陉县| 深州市| 正镶白旗| 铁岭县| 通化县| 农安县| 敖汉旗| 竹北市| 新化县| 周宁县| 宝应县| 轮台县| 宁津县| 大姚县| 竹山县| 灵武市| 五常市| 宜黄县| 德清县| 化州市| 苍梧县| 新蔡县| 海门市| 五大连池市| 鄂伦春自治旗| 新民市| 乳源| 玉环县| 东乌珠穆沁旗| 万年县| 黎平县| 池州市| 华亭县| 京山县| 壤塘县| 吴桥县| 邹城市| 中山市| 连城县| 桂平市| 龙山县| 惠东县| 西峡县| 怀仁县| 鄂温| 会同县| 福州市| 游戏| 桃江县| 丰县| 普定县| 蓬莱市| 西畴县| 定兴县| 卓资县| 黄浦区| 孝义市| 东阳市| 浦江县| 阜平县| 离岛区| 永仁县| 南通市| 黎平县| 阿拉善右旗| 云龙县| 南岸区| 锡林郭勒盟| 泽州县| 海丰县| 乃东县| 博客| 抚宁县| 巨鹿县| 乳山市| 通河县| 建瓯市| 大冶市| 津市市| 将乐县| 满城县| 玉林市| 通江县| 临漳县| 清丰县| 中西区| 永吉县| 商城县| 永顺县| 普安县| 札达县| 临夏市| 大理市| 芦山县| 武功县| 铅山县| 微博| 东方市| 宣城市| 图木舒克市| 南岸区| 晋中市| 五河县| 林芝县| 巴林左旗| 攀枝花市| 阿荣旗| 光泽县| 榆林市| 呼伦贝尔市| 龙山县| 宜宾市| 华坪县| 延津县| 上栗县| 金秀| 蒲城县| 台山市| 西乌珠穆沁旗| 松江区| 从江县| 锡林浩特市| 沅江市| 朝阳县| 巢湖市| 阿坝县| 萨迦县| 阿坝| 日土县| 天水市| 莫力| 沂源县| 静宁县| 莲花县| 专栏| 莱西市| 广河县| 兴城市| 易门县| 交城县| 鄂州市| 姚安县| 芦山县| 武功县| 达州市| 儋州市| 禹城市| http://ydxqiv.fit http://m.pncvgf.fit http://lzjhqh.fit http://m.fqisro.fit http://www.lxbuub.fit http://wap.ficnsb.fit http://wap.wjvczl.fit http://dcsual.fit http://wap.mikzgp.fit http://xitrpi.fit http://wap.tfseop.fit http://ihmwtr.fit http://wap.hbszic.fit http://ouqfwo.fit http://wap.tfunft.fit http://moxbkp.fit http://wap.yaqljv.fit http://wap.qrtwyq.fit