{"id":907,"date":"2023-04-16T23:04:55","date_gmt":"2023-04-16T14:04:55","guid":{"rendered":"http:\/\/mukgee.com\/?p=907"},"modified":"2023-04-16T23:04:55","modified_gmt":"2023-04-16T14:04:55","slug":"leetcode85-maximal-rectangle","status":"publish","type":"post","link":"http:\/\/mukgee.com\/?p=907","title":{"rendered":"[leetcode]85. Maximal Rectangle"},"content":{"rendered":"<p>\uc18d\ub3c4\ub294 \ub290\ub838\uc9c0\ub9cc Hard \ubb38\uc81c\ub97c \ud63c\uc790\uc11c \ud480\uc5c8\ub2e4\ub294\uc810\uc5d0 \uc810\uc218\ub97c \uc8fc\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4.<\/p>\n<p>https:\/\/leetcode.com\/problems\/maximal-rectangle<\/p>\n<p>&nbsp;<\/p>\n<p>\uc8fc\uc5b4\uc9c4 matrix \uc5d0\uc11c 1\ub9cc\uc73c\ub85c \uad6c\uc131\ub41c \uac00\uc7a5\ud070 rectangle\uc758 \ub113\uc774\ub97c \uad6c\ud558\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4.<\/p>\n<p>dp[i][j] \ub97c (i , j)\uc758 \uac00\uc7a5 \uae34 \uac00\ub85c\uc758 \uae38\uc774\ub85c \uc815\uc758\ud558\uace0 \ubb38\uc81c\ub97c \ud480\uc5c8\uc2b5\ub2c8\ub2e4.<\/p>\n<p>&nbsp;<\/p>\n<p>dp[i][j] = dp[i][j-1] +1 , if matrix[i][j] == 1<\/p>\n<p>0 , if matrix[i][j] != 1<\/p>\n<p>\uc774\ub807\uac8c matrix \uc548\uc5d0\uc11c \uac00\ub85c\uc758 \uae38\uc774\ub4e4\uc744 \uad6c\ud55c\ub4a4\uc5d0 \uac00\ub85c\uac00 \ub9cc\ub4e4\uc5b4\uc9c8\ub54c \uc704\ub85c \ud55c\uce78\uc529 \uac00\ub85c\ub4e4\uc744 \uc313\uc544 \uc62c\ub77c\uac00\uba74\uc11c \uc9c1\uc0ac\uac01\ud615\uc744 \ub9cc\ub4e4\uc5b4\ubd05\ub2c8\ub2e4.<\/p>\n<p><img loading=\"lazy\" width=\"1084\" height=\"400\" class=\"alignnone wp-image-908 size-full\" src=\"http:\/\/mukgee.com\/wp-content\/uploads\/2023\/04\/Pasted.png\" srcset=\"http:\/\/mukgee.com\/wp-content\/uploads\/2023\/04\/Pasted.png 1084w, http:\/\/mukgee.com\/wp-content\/uploads\/2023\/04\/Pasted-300x111.png 300w, http:\/\/mukgee.com\/wp-content\/uploads\/2023\/04\/Pasted-1024x378.png 1024w, http:\/\/mukgee.com\/wp-content\/uploads\/2023\/04\/Pasted-768x283.png 768w\" sizes=\"(max-width: 1084px) 100vw, 1084px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>\ud604\uc7ac \ube68\uac04\uc0c9 \uc9c0\uc810 ( i,j )\uc5d0 \uc788\ub2e4\uace0 \ud560\ub54c \ud604\uc7ac row\uc758 \uac00\uc7a5 \uae34 \uac00\ub85c\uc758 \uae38\uc774\ub97c 1\ucc28\ub85c \uad6c\ud558\uace0 dp \uc5d0 \uc800\uc7a5\ub41c dp[i-1][j] \ub85c \uc704\uc5d0 \uc313\uc778 \uac00\ub85c\ub4e4\uc758 \uae38\uc774\ub97c \ucc3e\uc544\uc11c \uac00\ub85c\ub97c \uc313\uc544\uc62c\ub824 \uc9c1\uc0ac\uac01\ud615\uc744 \ub9cc\ub4ed\ub2c8\ub2e4.<\/p>\n<p>\uc774\ub807\uac8c \ub9cc\ub4e4\uc5b4\uc9c4 \uc9c1\uc0ac\uac01\ud615\uc758 \ub113\uc774\ub97c \uad6c\ud558\uace0 \ud604\uc7ac \ucc3e\uc740 max \ub113\uc774 \uac12\uacfc \ube44\uad50\ud574\uc11c \uc815\ub2f5\uc774 \ub420 \uc218 \uc788\ub2e4\uba74 max \uac12\uc744 update \ud574\uc90d\ub2c8\ub2e4.<\/p>\n<p>&nbsp;<\/p>\n<pre class=\"lang:python decode:true \">class Solution(object):\r\n    def maximalRectangle(self, matrix):\r\n        \"\"\"\r\n        :type matrix: List[List[str]]\r\n        :rtype: int\r\n        \"\"\"\r\n        # dp[i][j] =&gt; i,j \uae4c\uc9c0\uc758 \uac00\ub85c \uae38\uc774\r\n        R , C = len(matrix) , len(matrix[0])\r\n        dp = [ [0]*C for _ in range(R)]\r\n        result = 0\r\n        for i in range(R):\r\n            for j in range(C):\r\n                if matrix[i][j] == \"1\" :\r\n                    dp[i][j] = dp[i][j-1] + 1\r\n                    y_val = 1\r\n                    x_val = dp[i][j]\r\n                    \r\n                    while True:\r\n                        result = max(result, x_val*y_val)  \r\n                        if i - y_val &lt; 0 :\r\n                            break\r\n                        if matrix[i- y_val][j] != \"1\" :\r\n                            break\r\n                        x_val = min(x_val , dp[i - y_val][j] )\r\n                        y_val += 1\r\n                        \r\n                    \r\n        return<\/pre>\n<p>&nbsp;<\/p>\n<p>\uc81c\uac00 \uc811\uadfc\ud55c \ubc29\ubc95\uc758 \uac00\uc7a5 \ud070 \ubb38\uc81c\ub294 \uac01 point \ub97c \uc811\uadfc\ud560\ub54c\ub9c8\ub2e4 \ub2e4\uc2dc \ud55c\ubc88 \uc704\ub85c \uc62c\ub77c\uac00\uba74\uc11c \uac00\ub2a5\ud55c \ubaa8\ub4e0 \uacbd\uc6b0\uc758 \uc218\ub97c \ud655\uc778\ud558\uae30 \ub54c\ubb38\uc5d0 O( M + N^2) \uc758 \uc2dc\uac04\ubcf5\uc7a1\ub3c4\ub97c \uac00\uc9c0\uac8c \ub429\ub2c8\ub2e4.<\/p>\n<p>\uc2e4\uc81c \uacb0\uacfc\ub3c4 pass\ub294 \ud588\uc9c0\ub9cc \uad49\uc7a5\ud788 \ub290\ub9b0 \uc18d\ub3c4\uc600\uc2b5\ub2c8\ub2e4.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" width=\"1674\" height=\"196\" class=\"alignnone wp-image-909 size-full\" src=\"http:\/\/mukgee.com\/wp-content\/uploads\/2023\/04\/Pasted-1.png\" srcset=\"http:\/\/mukgee.com\/wp-content\/uploads\/2023\/04\/Pasted-1.png 1674w, http:\/\/mukgee.com\/wp-content\/uploads\/2023\/04\/Pasted-1-300x35.png 300w, http:\/\/mukgee.com\/wp-content\/uploads\/2023\/04\/Pasted-1-1024x120.png 1024w, http:\/\/mukgee.com\/wp-content\/uploads\/2023\/04\/Pasted-1-768x90.png 768w, http:\/\/mukgee.com\/wp-content\/uploads\/2023\/04\/Pasted-1-1536x180.png 1536w\" sizes=\"(max-width: 1674px) 100vw, 1674px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>\uc0ac\uac01\ud615\uc744 \ud558\ub098\uc529 \uc313\uc544\uc62c\ub9b0\ub2e4\ub294 \uc811\uadfc\ubc95\uc740 \uc0dd\uac01\ud558\uae30\ub294 \uc26c\uc6e0\uc73c\ub098, \uc911\ubcf5 \uacc4\uc0b0\uc73c\ub85c \uc778\ud574 \uc131\ub2a5\uc5d0 \ubb38\uc81c\uac00 \uc788\ub124\uc694.<\/p>\n<p>&nbsp;<\/p>\n<p>\uc774\ubc88\uc5d0 chatGPT plus \ub97c \uc0ac\uc6a9\ud558\uac8c\ub418\uba74\uc11c GPT4\uc5d0\uac8c \ud55c\ubc88 \ubb3c\uc5b4\ubcf4\uc558\uc2b5\ub2c8\ub2e4.<\/p>\n<p>(GPT3\ub294 HARD \ubb38\uc81c\ub97c \uc798 \ud480\uc9c0 \ubabb\ud588\uc2b5\ub2c8\ub2e4.)<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" width=\"1582\" height=\"1698\" class=\"alignnone wp-image-910 size-full\" src=\"http:\/\/mukgee.com\/wp-content\/uploads\/2023\/04\/Pasted-2.png\" srcset=\"http:\/\/mukgee.com\/wp-content\/uploads\/2023\/04\/Pasted-2.png 1582w, http:\/\/mukgee.com\/wp-content\/uploads\/2023\/04\/Pasted-2-280x300.png 280w, http:\/\/mukgee.com\/wp-content\/uploads\/2023\/04\/Pasted-2-954x1024.png 954w, http:\/\/mukgee.com\/wp-content\/uploads\/2023\/04\/Pasted-2-768x824.png 768w, http:\/\/mukgee.com\/wp-content\/uploads\/2023\/04\/Pasted-2-1431x1536.png 1431w\" sizes=\"(max-width: 1582px) 100vw, 1582px\" \/><\/p>\n<p>&nbsp;<\/p>\n<pre class=\"lang:python decode:true\">class Solution:\r\n    def maximalRectangle(self, matrix: List[List[str]]) -&gt; int:\r\n        if not matrix or not matrix[0]:\r\n            return 0\r\n        \r\n        m, n = len(matrix), len(matrix[0])\r\n        heights = [0] * (n + 1)\r\n        max_area = 0\r\n        \r\n        for i in range(m):\r\n            for j in range(n):\r\n                heights[j] = heights[j] + 1 if matrix[i][j] == \"1\" else 0\r\n            \r\n            stack = [-1]\r\n            for j in range(n + 1):\r\n                while heights[j] &lt; heights[stack[-1]]:\r\n                    height = heights[stack.pop()]\r\n                    width = j - 1 - stack[-1]\r\n                    max_area = max(max_area, height * width)\r\n                stack.append(j)\r\n        \r\n        return max_area\r\n<\/pre>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>\uac00\uc7a5 \ub180\ub77c\uc6b4\uac74 \uc131\ub2a5\uc778\uac83 \uac19\uc2b5\ub2c8\ub2e4.<\/p>\n<p><img loading=\"lazy\" width=\"1676\" height=\"222\" class=\"alignnone wp-image-911 size-full\" src=\"http:\/\/mukgee.com\/wp-content\/uploads\/2023\/04\/Pasted-3.png\" srcset=\"http:\/\/mukgee.com\/wp-content\/uploads\/2023\/04\/Pasted-3.png 1676w, http:\/\/mukgee.com\/wp-content\/uploads\/2023\/04\/Pasted-3-300x40.png 300w, http:\/\/mukgee.com\/wp-content\/uploads\/2023\/04\/Pasted-3-1024x136.png 1024w, http:\/\/mukgee.com\/wp-content\/uploads\/2023\/04\/Pasted-3-768x102.png 768w, http:\/\/mukgee.com\/wp-content\/uploads\/2023\/04\/Pasted-3-1536x203.png 1536w\" sizes=\"(max-width: 1676px) 100vw, 1676px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>\uc81c \ucf54\ub4dc\uac00 100\uba85 \uc911\uc5d0 90 \ub4f1\uc774\uba74, GPT4\uc758 \ucf54\ub4dc\ub294 3\ub4f1\uc774\ub124\uc694.<\/p>\n<p>&nbsp;<\/p>\n<p>chatGPT \uac00 \uc81c\uacf5\ud55c solution \uc744 \uc0b4\ud3b4\ubcf4\uba74 O(N+M) \uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub97c \uac00\uc9c0\ub294 \ucf54\ub4dc\uc778\ub370\uc694.<\/p>\n<p>\uc6b0\uc120 row \ubcc4\ub85c loop\ub97c \ub3cc\uba74\uc11c \ud604\uc7ac row\uc5d0\uc11c \uac00\ub2a5\ud55c column \ubcc4 height \ub97c \uad00\ub9ac\ud569\ub2c8\ub2e4.<\/p>\n<pre class=\"lang:python decode:true\">for j in range(n): \r\n    heights[j] = heights[j] + 1 if matrix[i][j] == \"1\" else 0<\/pre>\n<p>&nbsp;<\/p>\n<p>\uadf8\ub9ac\uace0 height\uac00 \ubc14\ub00c\ub294 \uc9c0\uc810\uc5d0\uc11c height * width \ub97c \uacc4\uc0b0\ud574\uc11c \uacb0\uacfc\uac12\uc744 \ucc3e\uc544\ubd05\ub2c8\ub2e4.<\/p>\n<pre class=\"lang:python decode:true\">for j in range(n + 1): \r\n    while heights[j] &lt; heights[stack[-1]]: \r\n        height = heights[stack.pop()] \r\n        width = j - 1 - stack[-1] \r\n        max_area = max(max_area, height * width)<\/pre>\n<p>stack \uc758 \uac12\uc740 pointer \ucc98\ub7fc \ud604\uc7ac row\uc758 0\ubc88\uc9f8 index \ubd80\ud130 \ub9c8\uc9c0\ub9c9 index\uae4c\uc9c0 \ud0d0\uc0c9\ud574 \ub098\uac00\ub294\ub370,<\/p>\n<p>height \uac00 \ubcc0\uacbd\ub41c \uc9c0\uc810\uc740 pop \ucc98\ub9ac\ud574\uc11c width\ub97c \uad6c\ud560 \uc218 \uc788\ub3c4\ub85d \ub3c4\uc640\uc90d\ub2c8\ub2e4.<\/p>\n<p>&nbsp;<\/p>\n<p>\uc774 \uc54c\uace0\ub9ac\uc998\uc758 \uac00\uc7a5 \uc911\uc694\ud55c point \ub294<\/p>\n<blockquote><p><em>heights = [0] * <strong><span style=\"color: #ff0000;\">(n + 1)\u00a0<\/span><\/strong><\/em><\/p><\/blockquote>\n<p><span style=\"color: #ff0000;\"><span style=\"color: #000000;\">\uc774\ub77c\uace0 \uc0dd\uac01\ud569\ub2c8\ub2e4.<\/span><\/span><\/p>\n<p>&nbsp;<\/p>\n<p>heights\ub97c \uad00\ub9ac\ud560\ub54c column \uc0ac\uc774\uc988\ubcf4\ub2e4 +1 \ub85c \uad00\ub9ac\ud558\uba74\uc11c \ub9c8\uc9c0\ub9c9\uc5d0 0\uc73c\ub85c \ucc44\uc6cc\uc9c4 column \uc744 \ud558\ub098 \ucd94\uac00\ud569\ub2c8\ub2e4.<\/p>\n<p>column size +1 \uc744 \ud1b5\ud574\uc11c row\uc758 \ub9c8\uc9c0\ub9c9 width\ub97c \uacc4\uc0b0\ud560 \uc218 \uc788\uac8c \ub418\uc5b4 \uc815\ub2f5\uc744 \ucc3e\uc744 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n<p>&nbsp;<\/p>\n<p>\uc544\uc27d\uc9c0\ub9cc, \uc800\ub294 \uc544\uc9c1 chatGPT \uac00 \uc81c\uacf5\ud55c solution \ucc98\ub7fc \uc811\uadfc\ud560 \uc218 \uc788\ub294 \uc5ed\ub7c9\uc774 \uc548\ub429\ub2c8\ub2e4.<\/p>\n<p>\ud558\uc9c0\ub9cc, \ub2e4\uc591\ud55c \ubb38\uc81c\ub97c \ud480\uc5b4\ubcf4\uba74\uc11c chatGPT\ub4e0, \ub2e4\ub978 \uc0ac\ub78c\ub4e4\uc758 \ucf54\ub4dc\ub4e0 \uc5ec\ub7ec \uc811\uadfc \ubc29\ubc95\uc5d0 \ub300\ud574 \uace0\ubbfc\ud558\uace0 \uc0dd\uac01\uc744 \ub113\ud600 \ub098\uac00\uc57c\ud560 \uac83 \uac19\uc2b5\ub2c8\ub2e4.<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\uc18d\ub3c4\ub294 \ub290\ub838\uc9c0\ub9cc Hard \ubb38\uc81c\ub97c \ud63c\uc790\uc11c \ud480\uc5c8\ub2e4\ub294\uc810\uc5d0 \uc810\uc218\ub97c \uc8fc\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4. https:\/\/leetcode.com\/problems\/maximal-rectangle &nbsp; \uc8fc\uc5b4\uc9c4 matrix \uc5d0\uc11c 1\ub9cc\uc73c\ub85c \uad6c\uc131\ub41c \uac00\uc7a5\ud070 rectangle\uc758 \ub113\uc774\ub97c \uad6c\ud558\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4. dp[i][j] \ub97c (i ,&hellip;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":""},"categories":[3],"tags":[81,83],"aioseo_notices":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/posts\/907"}],"collection":[{"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/mukgee.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=907"}],"version-history":[{"count":1,"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/posts\/907\/revisions"}],"predecessor-version":[{"id":912,"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/posts\/907\/revisions\/912"}],"wp:attachment":[{"href":"http:\/\/mukgee.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=907"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/mukgee.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=907"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/mukgee.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=907"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}