{"id":3128,"date":"2020-03-06T10:58:25","date_gmt":"2020-03-06T02:58:25","guid":{"rendered":"http:\/\/www.sniper97.cn\/?p=3128"},"modified":"2020-03-06T10:58:25","modified_gmt":"2020-03-06T02:58:25","slug":"%e3%80%90leetcode%e3%80%910085-%e6%9c%80%e5%a4%a7%e7%9f%a9%e5%bd%a2","status":"publish","type":"post","link":"http:\/\/www.sniper97.cn\/index.php\/note\/algorithm\/3128\/","title":{"rendered":"\u3010LeetCode\u3011*0085 \u6700\u5927\u77e9\u5f62"},"content":{"rendered":"\n<p><a href=\"https:\/\/leetcode-cn.com\/problems\/maximal-rectangle\/\">https:\/\/leetcode-cn.com\/problems\/maximal-rectangle\/<\/a><\/p>\n\n\n<pre class=\"wp-block-preformatted\"># -*- coding:utf-8 -*-\n<em>\n<\/em>class Solution(object):\n    def maximalRectangle(self, matrix):\n        <em>\"\"\"\n        <\/em><strong><em>:type<\/em><\/strong><em> matrix: List[List[str]]\n        <\/em><strong><em>:rtype<\/em><\/strong><em>: int\n        \"\"\"\n        <\/em>if not matrix: return 0\n        m = len(matrix)\n        n = len(matrix[0])\n        left = [0] * n  # initialize left as the leftmost boundary possible\n        right = [n] * n  # initialize right as the rightmost boundary possible\n        height = [0] * n\n        maxarea = 0\n        for i in range(m):\n            cur_left, cur_right = 0, n\n            # update height\n            for j in range(n):\n                if matrix[i][j] == '1':\n                    height[j] += 1\n                else:\n                    height[j] = 0\n            # update left\n            for j in range(n):\n                if matrix[i][j] == '1':\n                    left[j] = max(left[j], cur_left)\n                else:\n                    left[j] = 0\n                    cur_left = j + 1\n            # update right\n            for j in range(n - 1, -1, -1):\n                if matrix[i][j] == '1':\n                    right[j] = min(right[j], cur_right)\n                else:\n                    right[j] = n\n                    cur_right = j\n            # update the area\n            for j in range(n):\n                maxarea = max(maxarea, height[j] * (right[j] - left[j]))\n        return maxarea\nif __name__ == '__main__':\n    matrix = [\n        [\"1\", \"0\", \"0\", \"0\", \"0\"],\n        [\"1\", \"0\", \"1\", \"1\", \"1\"],\n        [\"1\", \"1\", \"1\", \"1\", \"1\"],\n        [\"1\", \"0\", \"0\", \"1\", \"0\"]\n    ]\n    print(Solution().maximalRectangle(matrix))\n<\/pre>\n\n\n<p><strong>\u601d\u8def<\/strong>\uff1a\u8fd9\u9053\u9898\u4e00\u770b\u5c31\u611f\u89c9\u662f\u52a8\u6001\u89c4\u5212\uff0c\u4f46\u662f\u52a8\u6001\u89c4\u5212\u5176\u5b9e\u96be\u5c31\u96be\u5728\u627e\u72b6\u6001\uff0c\u8fd9\u9053\u9898\u6211\u601d\u8003\u4e86\u5f88\u4e45\u5c1d\u8bd5\u627e\u51fa\u72b6\u6001\uff0c\u521a\u5f00\u59cb\u60f3\u7684\u5c31\u662fmax area\uff0c\u540e\u6765\u53d1\u73b0\u4e0d\u884c\uff0c\u8981\u5e26\u8fb9\u72b6\u6001\uff0c\u7136\u540e\u53c8\u5c1d\u8bd5m*n,area\u7684\u7ec4\u5408\uff0c\u4f46\u662f\u4f9d\u7136\u4e0d\u884c\u3002<\/p>\n\n\n<p>\u6700\u540e\u770b\u9898\u89e3\u53d1\u73b0\u8fd9\u9053\u9898\u6709\u4e24\u79cddp\u601d\u8def\uff0c\u4e00\u79cd\u662f\u8f83\u5dee\u7684\u3002<\/p>\n\n\n<p>\u5bf9\u6bcf\u4e00\u884c\u8fde\u7eed\u76841\u8fdb\u884c\u5224\u65ad\uff0c\u7136\u540e\u5728\u5224\u65ad\u6700\u5927\u77e9\u5f62\uff0c\u4e5f\u5c31\u662f\u5728\u957f\u5bbd\u76f8\u540c\u7684\u77e9\u9635\u4e2d\u590d\u6742\u5ea6\u8fbe\u5230\u4e86n3\u3002<\/p>\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" width=\"768\" height=\"584\" src=\"\/wp-content\/uploads\/2020\/03\/\u56fe\u7247-11.png\" alt=\"\" class=\"wp-image-3129\" srcset=\"http:\/\/www.sniper97.cn\/wp-content\/uploads\/2020\/03\/\u56fe\u7247-11.png 768w, http:\/\/www.sniper97.cn\/wp-content\/uploads\/2020\/03\/\u56fe\u7247-11-300x228.png 300w\" sizes=\"(max-width: 768px) 100vw, 768px\" \/><\/figure><\/div>\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" width=\"729\" height=\"590\" src=\"\/wp-content\/uploads\/2020\/03\/\u56fe\u7247-12.png\" alt=\"\" class=\"wp-image-3130\" srcset=\"http:\/\/www.sniper97.cn\/wp-content\/uploads\/2020\/03\/\u56fe\u7247-12.png 729w, http:\/\/www.sniper97.cn\/wp-content\/uploads\/2020\/03\/\u56fe\u7247-12-300x243.png 300w\" sizes=\"(max-width: 729px) 100vw, 729px\" \/><\/figure><\/div>\n\n\n<p>\u7b2c\u4e8c\u79cd\u8f83\u597d\u7684\u601d\u60f3\u590d\u6742\u5ea6\u5728\u77e9\u9635\u4e2d\u8fbe\u5230\u4e86n2\u3002<\/p>\n\n\n<p>\u627e\u5de6\u8fb9\u7b2c\u4e00\u4e2a\u975e1\u4f4d\u7f6e\u548c\u53f3\u8fb9\u7b2c\u4e00\u4e2a\u975e1\u4f4d\u7f6e\uff0c\u90a3\u4e48\u6700\u5927\u7684\u533a\u57df\u5c31\u53ef\u4ee5\u88ab\u5de6\u53f3\u4e24\u4e2a\u5939\u51fa\u6765\uff0c\u5728\u6dfb\u52a0\u4e00\u4e2a\u9ad8\u5ea6\u5217\u8868\uff0c\u5c31\u53ef\u4ee5\u7b97\u51fa\u6700\u5927\u77e9\u9635\u3002<\/p>\n\n\n<p>\u5982\u4e0b\u56fe\uff0c\u6211\u4eec\u865a\u62df\u51fa\u6765\u4e00\u4e2a\u7b2c\u4e94\u5217\uff0c\u5047\u5982\u6211\u4eec\u7b97\u5728\u7b2c2\u884c\uff0c\u56e0\u6b64\u6709height\u3001left\u3001right\u5982\u53f3\u8fb9\u6240\u793a\uff1a<\/p>\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" width=\"881\" height=\"261\" src=\"\/wp-content\/uploads\/2020\/03\/\u56fe\u7247-15.png\" alt=\"\" class=\"wp-image-3133\" srcset=\"http:\/\/www.sniper97.cn\/wp-content\/uploads\/2020\/03\/\u56fe\u7247-15.png 881w, http:\/\/www.sniper97.cn\/wp-content\/uploads\/2020\/03\/\u56fe\u7247-15-300x89.png 300w, http:\/\/www.sniper97.cn\/wp-content\/uploads\/2020\/03\/\u56fe\u7247-15-768x228.png 768w\" sizes=\"(max-width: 881px) 100vw, 881px\" \/><\/figure><\/div>\n\n\n<p>\u5bf9\u4e8eheight\uff0c\u5c31\u662f\u8fde\u7eed\u591a\u5c11\u4e2a1\uff0c\u5bf9\u4e8eleft\u662f\u5f53\u524d\u5217\u5728\u4e4b\u524d\u51fa\u73b0\u8fc7\u7684\u884c\u4e2d\u6700\u5927\u76841\u7d22\u5f15\uff0c\u4e5f\u5c31\u662f\u5c3d\u53ef\u80fd\u9760\u53f3\uff0c\u7136\u540eright\u540c\u7406\uff0c\u8fd9\u65f6\u5019\u6211\u4eec\u5c31\u5728\u8fd9\u884c\u53ef\u4ee5\u6c42\u51fa\u6700\u5927\u77e9\u5f62\u9762\u79ef( right-left )*height = \uff08 5-2 \uff09*2<\/p>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/leetcode-cn.com\/problems\/maximal-rectangle [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_mi_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[10],"tags":[],"views":3536,"_links":{"self":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts\/3128"}],"collection":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/comments?post=3128"}],"version-history":[{"count":0,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts\/3128\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/media?parent=3128"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/categories?post=3128"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/tags?post=3128"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}