{"id":182,"date":"2023-08-05T17:56:49","date_gmt":"2023-08-05T09:56:49","guid":{"rendered":"http:\/\/lingbo.online\/?p=182"},"modified":"2023-09-01T12:44:10","modified_gmt":"2023-09-01T04:44:10","slug":"leecode_array","status":"publish","type":"post","link":"https:\/\/lingbo.online\/index.php\/algorithm_learning\/leecode_array\/","title":{"rendered":"LeeCode\u7b97\u6cd5\u603b\u7ed3\u2014\u2014\u6570\u7ec4\/\u5b57\u7b26\u4e32"},"content":{"rendered":"<h3>LeeCode.135 \u5206\u53d1\u7cd6\u679c<\/h3>\n<h4>\u9898\u76ee\u63cf\u8ff0<\/h4>\n<p>\u9898\u76ee\u94fe\u63a5\uff1a<a href=\"https:\/\/leetcode.cn\/problems\/candy\/?envType=study-plan-v2&amp;envId=top-interview-150\" target=\"_blank\"  rel=\"nofollow\" >https:\/\/leetcode.cn\/problems\/candy\/?envType=study-plan-v2&envId=top-interview-150<\/a><br \/>\n<code>n<\/code>\u4e2a\u5b69\u5b50\u7ad9\u6210\u4e00\u6392\uff0c\u7ed9\u5b9a\u4e00\u4e2a\u6574\u6570\u6570\u7ec4\u8868\u793a\u6bcf\u4e2a\u5b69\u5b50\u7684\u8bc4\u5206\u3002<br \/>\n\u4f60\u9700\u8981\u6309\u7167\u4ee5\u4e0b\u8981\u6c42\uff0c\u7ed9\u8fd9\u4e9b\u5b69\u5b50\u5206\u53d1\u7cd6\u679c\uff1a<\/p>\n<ul>\n<li>\u6bcf\u4e2a\u5b69\u5b50\u81f3\u5c11\u5206\u914d\u5230<code>1<\/code>\u4e2a\u7cd6\u679c\u3002<\/li>\n<li>\u76f8\u90bb\u4e24\u4e2a\u5b69\u5b50\uff0c\u8bc4\u5206\u66f4\u9ad8\u7684\u5b69\u5b50\u4f1a\u83b7\u5f97\u66f4\u591a\u7684\u7cd6\u679c<br \/>\n\u8bf7\u7ed9\u6bcf\u4e2a\u5b69\u5b50\u5206\u53d1\u7cd6\u679c\uff0c\u8ba1\u7b97\u5e76\u8fd4\u56de\u9700\u8981\u51c6\u5907\u7684\u6700\u5c11\u7cd6\u679c\u6570\u76ee\u3002<\/li>\n<\/ul>\n<p>\u793a\u4f8b\u4e00\uff1a<\/p>\n<pre><code>\u8f93\u5165\uff1aratings=[1,0,2]\n\u8f93\u51fa\uff1a5\n\u89e3\u91ca\uff1a\u4f60\u53ef\u4ee5\u5206\u522b\u7ed9\u7b2c\u4e00\u4e2a\u3001\u7b2c\u4e8c\u4e2a\u3001\u7b2c\u4e09\u4e2a\u5b69\u5b50\u5206\u53d12\u30011\u30012\u9897\u7cd6\u679c<\/code><\/pre>\n<p>\u793a\u4f8b\u4e8c\uff1a<\/p>\n<pre><code>\u8f93\u5165\uff1aratings=[1,2,2]\n\u8f93\u51fa\uff1a4\n\u89e3\u91ca\uff1a\u4f60\u53ef\u4ee5\u5206\u522b\u7ed9\u7b2c\u4e00\u4e2a\u3001\u7b2c\u4e8c\u4e2a\u3001\u7b2c\u4e09\u4e2a\u5b69\u5b50\u5206\u522b\u5206\u53d11\u30012\u30011\u9897\u7cd6\u679c\u3002\n\u7b2c\u4e09\u4e2a\u5b69\u5b50\u53ea\u5f97\u52301\u9897\u7cd6\u679c\uff0c\u6ee1\u8db3\u9898\u9762\u4e2d\u7684\u4e24\u4e2a\u6761\u4ef6\u3002<\/code><\/pre>\n<p>\u63d0\u793a\uff1a<\/p>\n<ul>\n<li><code>n==rating.length<\/code><\/li>\n<li><code>1&lt;=n&lt;=2*10^4<\/code><\/li>\n<li><code>0&lt;=rating[i]&lt;=2*10^4<\/code><\/li>\n<\/ul>\n<h4>\u89e3\u9898\u601d\u8def<\/h4>\n<p>\u8003\u8651\u4f7f\u7528\u8d2a\u5fc3\u7684\u601d\u60f3\u8fdb\u884c\u6c42\u89e3\uff0c\u5373\u5bf9\u5bf9\u76f8\u90bb\u7684\u5b66\u751f<code>A<\/code>\u548c\u5b66\u751f<code>B<\/code>(<code>A<\/code>\u5728<code>B<\/code>\u5de6\u4fa7)\uff0c\u5e94\u8be5\u6ee1\u8db3\uff1a<\/p>\n<ul>\n<li>\u5982\u679cratings_B&gt;ratings_A\uff0cB\u7684\u7cd6\u679c\u6bd4A\u591a<\/li>\n<li>\u5982\u679crating_A&gt;ratings_B\uff0cA\u7684\u7cd6\u679c\u6bd4B\u591a<\/li>\n<\/ul>\n<p>\u56e0\u6b64\uff0c\u8981\u5f97\u51fa\u6ee1\u8db3\u9898\u76ee\u8981\u6c42\u7684\u7b54\u6848\uff0c\u53ef\u4ee5\u5206\u522b\u4ece\u5de6\u5230\u53f3\u3001\u4ece\u53f3\u5230\u5de6\u904d\u5386\u4e24\u6761\u89c4\u5219\uff0c\u53d6\u4e8c\u8005\u7684\u6700\u5927\u503c\uff0c\u4ece\u800c\u6ee1\u8db3\u9898\u76ee\u6761\u4ef6\u3002<\/p>\n<h4>\u7b97\u6cd5\u6d41\u7a0b<\/h4>\n<ol>\n<li>\u9996\u5148\u4ece\u5de6\u5230\u53f3\u904d\u5386<code>ratings<\/code>\uff0c\u5c06\u7cd6\u679c\u8bb0\u5f55\u5728<code>left_list<\/code>\u4e2d<br \/>\n1.\u5148\u7ed9\u6240\u6709\u5b66\u751f\u4e00\u9897\u7cd6\uff1b<\/p>\n<ol start=\"2\">\n<li>\u5bf9\u4e8e\u5b66\u751f<code>i<\/code>\u6765\u8bf4\uff0c\u5982\u679c\u76f8\u90bb\u53f3\u4fa7<code>i+1<\/code>\u5b66\u751f\u7684\u5206\u6570\u66f4\u9ad8\uff0c\u5219\u5c06\u5176\u7cd6\u679c\u6570\u91cf\u66f4\u6539\u4e3a<code>left_list[i]+1<\/code>\uff1b<\/li>\n<li>\u5982\u679c\u5b66\u751f<code>i+1<\/code>\u7684\u5206\u6570\u6bd4\u5b66\u751f<code>i<\/code>\u4f4e\uff0c\u4e0d\u505a\u5904\u7406\uff08\u5728\u7b2c\u4e8c\u8f6e\u904d\u5386\u4e2d\u5904\u7406\uff09\u3002<\/li>\n<\/ol>\n<\/li>\n<li>\u63a5\u7740\u4ece\u53f3\u5230\u5de6\u904d\u5386\u5b66\u751f\u5c42\u7ea7\uff0c\u5c06\u7cd6\u679c\u6570\u91cf\u8bb0\u5f55\u5728<code>right_list<\/code>\u4e2d\uff0c\u5b8c\u6210\u5bf9\u7b2c\u4e8c\u6761\u89c4\u5219\u7684\u5339\u914d\u3002<\/li>\n<li>\u53d6<code>left_list<\/code>\u548c<code>right_list<\/code>\u6bcf\u4e2a\u5143\u7d20\u7684\u6700\u5927\u503c\uff0c\u8be5\u503c\u53ef\u4ee5\u540c\u65f6\u6ee1\u8db3\u4e0a\u8ff0\u4e24\u6761\u89c4\u5219\uff0c<code>sum<\/code>\u540e\u5373\u5f97\u5230\u6bcf\u4e2a\u540c\u5b66\u7684\u6700\u5c11\u7cd6\u679c\u6570\u91cf\u3002<\/li>\n<\/ol>\n<h4>\u590d\u6742\u5ea6\u5206\u6790<\/h4>\n<ul>\n<li>\u7a7a\u95f4\u590d\u6742\u5ea6O\uff08N\uff09\uff1a\u5efa\u7acb\u4e86\u4e24\u4e2a\u957f\u5ea6\u4e3an\u7684\u5217\u8868\u4fdd\u5b58\u4e24\u8f6e\u904d\u5386\u7684\u7cd6\u679c\u6570\u91cf<\/li>\n<li>\u65f6\u95f4\u590d\u6742\u5ea6O\uff08N\uff09\uff1a\u4e24\u8f6e\u904d\u5386\uff0c\u6ca1\u6709\u5d4c\u5957<\/li>\n<\/ul>\n<h4>\u89e3\u9898\u4ee3\u7801<\/h4>\n<pre><code class=\"language-python\">class Solution:\n    def candy(self, ratings: List[int]) -&gt; int:\n        n=len(ratings)\n        left_list=[1]*n\n        right_list=[1]*n\n\n        #\u904d\u5386\u5de6\u89c4\u5219\n        for i in range(1,n):\n            if ratings[i]&gt;ratings[i-1]:\n                left_list[i]=left_list[i-1]+1\n\n        count=left_list[-1]\n\n        #\u904d\u5386\u53f3\u89c4\u5219\n        for i in range(n-2,-1,-1):\n            if ratings[i]&gt;ratings[i+1]:\n                right_list[i]=right_list[i+1]+1\n            count+=max(left_list[i],right_list[i])\n\n        return count<\/code><\/pre>\n<h3>LeeCode.42 \u63a5\u96e8\u6c34<\/h3>\n<h4>\u9898\u76ee\u63cf\u8ff0<\/h4>\n<p>\u9898\u76ee\u94fe\u63a5\uff1a<a href=\"https:\/\/leetcode.cn\/problems\/trapping-rain-water\/description\/?envType=study-plan-v2&amp;envId=top-interview-150\" target=\"_blank\"  rel=\"nofollow\" >https:\/\/leetcode.cn\/problems\/trapping-rain-water\/description\/?envType=study-plan-v2&envId=top-interview-150<\/a><br \/>\n\u7ed9\u5b9a<code>n<\/code>\u4e2a\u975e\u8d1f\u6574\u6570\u8868\u793a\u6bcf\u4e2a\u5bbd\u5ea6\u4e3a<code>1<\/code>\u7684\u67f1\u5b50\u7684\u9ad8\u5ea6\u56fe\uff0c\u8ba1\u7b97\u6309\u6b64\u6392\u5217\u7684\u67f1\u5b50\uff0c\u4e0b\u96e8\u4e4b\u540e\u80fd\u63a5\u591a\u5c11\u96e8\u6c34\u3002<\/p>\n<p><strong>\u793a\u4f8b1\uff1a<\/strong><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/lingbo.online\/wp-content\/uploads\/2023\/08\/rainwatertrap.png\" alt=\"\" \/><\/p>\n<pre><code>\u8f93\u5165\uff1aheight=[0,1,0,2,1,0,1,3,2,1,2,1]\n\u8f93\u51fa\uff1a6\n\u89e3\u91ca\uff1a\u4e0a\u9762\u662f\u7531\u6570\u7ec4 [0,1,0,2,1,0,1,3,2,1,2,1] \u8868\u793a\u7684\u9ad8\u5ea6\u56fe\uff0c\u5728\u8fd9\u79cd\u60c5\u51b5\u4e0b\uff0c\u53ef\u4ee5\u63a5 6 \u4e2a\u5355\u4f4d\u7684\u96e8\u6c34\uff08\u84dd\u8272\u90e8\u5206\u8868\u793a\u96e8\u6c34\uff09\u3002<\/code><\/pre>\n<h4>\u89e3\u9898\u601d\u8def<\/h4>\n<p>\u5bf9\u4e8e\u4e0b\u6807i\uff0c\u4e0b\u96e8\u540e\u80fd\u591f\u8fbe\u5230\u7684\u6700\u5927\u9ad8\u5ea6\u7b49\u4e8e\u4e0b\u6807i\u4e24\u8fb9\u9ad8\u5ea6\u7684\u6700\u5c0f\u503c\uff0c\u4e0b\u6807i\u5904\u80fd\u591f\u5b58\u50a8\u7684\u96e8\u91cf\u7b49\u4e8e\u4e0b\u6807i\u5904\u6c34\u80fd\u8fbe\u5230\u7684\u6700\u5927\u9ad8\u5ea6\u51cf\u53bbheight[i]\uff0c\u56e0\u6b64\uff0c\u5728\u89e3\u9898\u65f6\uff0c\u53ef\u4ee5\u5206\u522b\u904d\u5386\u4e0b\u6807i\u5de6\u4fa7\u548c\u53f3\u4fa7\u7684\u6700\u5927\u9ad8\u5ea6\uff0c\u7136\u540e\u8ba1\u7b97\u6bcf\u4e2a\u4e0b\u6807\u4f4d\u7f6e\u80fd\u63a5\u7684\u96e8\u6c34\u91cf\uff0c\u8003\u8651\u4f7f\u7528\u52a8\u6001\u89c4\u5212\u7684\u65b9\u6cd5\u51cf\u5c11\u8ba1\u7b97\u590d\u6742\u5ea6\u3002<\/p>\n<ol>\n<li>\u521b\u5efa\u4e24\u4e2a\u957f\u5ea6\u4e3an\u7684\u6570\u7ec4leftMax\u548crightMax\uff0c\u5206\u522b\u8868\u793a\u5de6\u4fa7\u548c\u53f3\u4fa7\u7684\u6700\u5927\u9ad8\u5ea6<\/li>\n<li>\u5bf9leftMax\u8fdb\u884c\u6b63\u5411\u904d\u5386\uff0c\u521d\u503c\u4e3aheight[0]\uff0c\u5bf9rightMax\u8fdb\u884c\u53cd\u5411\u904d\u5386\uff0c\u521d\u503c\u4e3aheight[n-1]\uff0c\u904d\u5386\u65b9\u6cd5\u5982\u4e0b\uff1a\n<ul>\n<li>\u5f53<span class=\"katex-eq\" data-katex-display=\"false\">1\/leqi\/leqn-1<\/span>\u65f6\uff0cleftMax[i]=max(leftMax[i-1],height[i]);<\/li>\n<li>\u5f53<span class=\"katex-eq\" data-katex-display=\"false\">0\/leqi\/leqn-2<\/span>\u65f6\uff0crightMax[i]=max(rightMax[i+1],height[i])<\/li>\n<\/ul>\n<\/li>\n<li>\u5728\u5f97\u5230\u6570\u7ec4leftMax\u548crightMax\u7684\u6bcf\u4e2a\u5143\u7d20\u503c\u540e\uff0c\u4e0b\u6807i\u51fa\u80fd\u63a5\u7684\u96e8\u6c34\u91cf\u7b49\u4e8emin(leftMax[i],rightMax[i])-height[i]\uff0c\u904d\u5386\u6bcf\u4e2a\u4e0b\u6807\u65e2\u5f97\u5230\u96e8\u6c34\u603b\u91cf<\/li>\n<\/ol>\n<p>\u5b98\u65b9\u6c42\u89e3\u4e2d\u7ed9\u51fa\u4e86\u8be5\u95ee\u9898\u7684\u6c42\u89e3\u56fe\u7247\u793a\u4f8b\uff1a<br \/>\n<img decoding=\"async\" src=\"https:\/\/lingbo.online\/wp-content\/uploads\/2023\/08\/1.png\" alt=\"\" \/><\/p>\n<h4>\u590d\u6742\u5ea6\u5206\u6790<\/h4>\n<ul>\n<li><strong>\u65f6\u95f4\u590d\u6742\u5ea6<\/strong>\uff1aO(n)<\/li>\n<li><strong>\u7a7a\u95f4\u590d\u6742\u5ea6<\/strong>\uff1aO(n)<\/li>\n<\/ul>\n<h4>\u793a\u4f8b\u4ee3\u7801<\/h4>\n<pre><code class=\"language-python\">class Solution:\n    def trap(self, height: List[int]) -&gt; int:\n        if not height:\n            return 0\n\n        n=len(height)\n\n        #\u5bf9\u5de6\u4fa7\u6700\u5927\u503c\u8d4b\u521d\u59cb\u503c\n        leftMax=[height[0]]+[0]*(n-1)\n\n        for i in range(1,n):\n            leftMax[i]=max(leftMax[i-1],height[i])\n\n        #\u5bf9\u53f3\u4fa7\u6700\u5927\u503c\u8d4b\u521d\u503c\n        rightMax=[0]*(n-1)+[height[n-1]]\n\n        for i in range(n-2,-1,-1):\n            rightMax[i]=max(rightMax[i+1],height[i])\n\n        return sum(min(leftMax[i],rightMax[i])-height[i] for i in range(n))\n<\/code><\/pre>\n<h3>\u6700\u5c0f\u77e9\u9635\u4e58\u6cd5\u6b21\u6570<\/h3>\n<h4>\u9898\u76ee\u63cf\u8ff0<\/h4>\n<p>\u6c42\u89e3n\u4e2a\u77e9\u9635\u7684\u8fde\u4e58\u6240\u9700\u8981\u7684\u6700\u5c0f\u4e58\u6cd5\u6b21\u6570<\/p>\n<h4>\u89e3\u9898\u601d\u8def<\/h4>\n<ol>\n<li>\u9996\u5148\uff0c\u521d\u59cb\u5316\u957f\u5ea6\u4e3a1\u7684\u8fde\u4e58\u77e9\u9635\u7684\u4e58\u6cd5\u6b21\u6570\u90fd\u4e3a\u96f6\uff0c\u56e0\u4e3a\u77e9\u9635\u672c\u8eab\u4e0d\u9700\u8981\u4e58\u6cd5<\/li>\n<li>\u904d\u5386\u5206\u5272\u70b9k\uff0c\u8ba1\u7b97\u4e24\u90e8\u5206\u7684\u4e58\u6cd5\u6b21\u6570\uff0c\u5e76\u52a0\u4e0a\u5f53\u524d\u77e9\u9635\u4e58\u6cd5\u7684\u6b21\u6570<\/li>\n<li>\u8fd4\u56dedp[1][n-1]\uff0c\u5373\u4e3a\u6240\u6709\u77e9\u9635\u8fde\u4e58\u6240\u9700\u8981\u7684\u6700\u5c0f\u4e58\u6cd5\u6b21\u6570<\/li>\n<\/ol>\n<h4>\u89e3\u9898\u4ee3\u7801<\/h4>\n<pre><code class=\"language-python\">def matrixChainOrder(p):\n    n=len(p) # \u77e9\u9635\u4e2a\u6570\n    dp=[[0]*n for _ in range(n)]\n\n    # \u521d\u59cb\u5316\u957f\u5ea6\u4e3a1\u7684\u8fde\u4e58\u77e9\u9635\u7684\u4e58\u6cd5\u6b21\u6570\u90fd\u4e3a0\n    for i in range(1,n):\n        dp[i][i]=0\n\n    # \u9010\u4e2a\u8ba1\u7b97\u4e0d\u540c\u8fde\u4e58\u94fe\u957f\u5ea6\u7684\u6700\u5c0f\u4e58\u6cd5\u6b21\u6570\n    for L in range(2,n):\n        for i in range(1,n-L+1):\n            j=L+i-1\n            dp[i][j]=float(&#039;inf&#039;) # \u521d\u59cb\u5316\u6b21\u6570\u4e3a\u6b63\u65e0\u7a77\n\n            # \u8ba1\u7b97\u4e0d\u540c\u5206\u5272\u70b9\u4e0b\u7684\u6700\u5c0f\u4e58\u6cd5\u6b21\u6570\n            for k in range(i,j):\n                count=dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j]\n                if count&lt;dp[i][j]:\n                    dp[i][j]=count\n\n    # \u8fd4\u56de\u6240\u6709\u77e9\u9635\u8fde\u4e58\u7684\u6700\u5c0f\u4e58\u6cd5\u6b21\u6570\n    return dp[1][n-1]<\/code><\/pre>\n<h3>Leecode 152. \u4e58\u79ef\u6700\u5927\u5b50\u5e8f\u5217<\/h3>\n<h4>\u9898\u76ee\u63cf\u8ff0<\/h4>\n<p>\u9898\u76ee\u94fe\u63a5\uff1a<a href=\"https:\/\/leetcode.cn\/problems\/maximum-product-subarray\/description\/\" target=\"_blank\"  rel=\"nofollow\" >https:\/\/leetcode.cn\/problems\/maximum-product-subarray\/description\/<\/a><\/p>\n<p>\u7ed9\u4f60\u4e00\u4e2a\u6574\u6570\u6570\u7ec4 nums \uff0c\u8bf7\u4f60\u627e\u51fa\u6570\u7ec4\u4e2d\u4e58\u79ef\u6700\u5927\u7684\u975e\u7a7a\u8fde\u7eed\u5b50\u6570\u7ec4\uff08\u8be5\u5b50\u6570\u7ec4\u4e2d\u81f3\u5c11\u5305\u542b\u4e00\u4e2a\u6570\u5b57\uff09\uff0c\u5e76\u8fd4\u56de\u8be5\u5b50\u6570\u7ec4\u6240\u5bf9\u5e94\u7684\u4e58\u79ef\u3002<\/p>\n<p>\u6d4b\u8bd5\u7528\u4f8b\u7684\u7b54\u6848\u662f\u4e00\u4e2a<strong>32-\u4f4d<\/strong>\u6574\u6570\u3002<\/p>\n<p><strong>\u5b50\u6570\u7ec4<\/strong>\u662f\u6570\u7ec4\u7684\u8fde\u7eed\u5b50\u5e8f\u5217\u3002<\/p>\n<p>\u793a\u4f8b1\uff1a<\/p>\n<ul>\n<li>\u8f93\u5165\uff1anums=[2,3,-2,4]<\/li>\n<li>\u8f93\u51fa\uff1a6<\/li>\n<li>\u89e3\u91ca\uff1a\u5b50\u6570\u7ec4[2,3]\u6709\u6700\u5927\u4e58\u79ef6<\/li>\n<\/ul>\n<p>\u793a\u4f8b2\uff1a<\/p>\n<ul>\n<li>\u8f93\u5165\uff1anums=[-2,0,-1]<\/li>\n<li>\u8f93\u51fa\uff1a0<\/li>\n<li>\u89e3\u91ca\uff1a\u7ed3\u679c\u4e0d\u80fd\u4e3a2\uff0c\u56e0\u4e3a[-2,-1]\u4e0d\u662f\u5b50\u6570\u7ec4<\/li>\n<\/ul>\n<h4>\u89e3\u9898\u601d\u8def<\/h4>\n<p>\u8003\u8651\u4f7f\u7528\u52a8\u6001\u89c4\u5212\u65b9\u6cd5\u6c42\u89e3\uff0c\u5177\u4f53\u601d\u8def\u4e3a\uff1a<\/p>\n<ol>\n<li>\u904d\u5386\u6570\u7ec4\u65f6\u8ba1\u7b97\u5f53\u524d\u6700\u5927\u503c\uff0c\u4e0d\u65ad\u66f4\u65b0<\/li>\n<li>\u4ee4<code>max_result[i]<\/code>\u4e3a\u5f53\u524d\u7684\u6700\u5927\u503c\uff0c\u5219\u8be5\u52a8\u6001\u89c4\u5212\u7684\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\u53ef\u4ee5\u8868\u793a\u4e3a\uff1a<code>max_result[i]=max(nums[i],max_result[i-1]*nums[i])<\/code><\/li>\n<li>\u7531\u4e8e\u5b58\u5728\u8d1f\u6570\uff0c\u90a3\u4e48\u4f1a\u5bfc\u81f4\u6700\u5927\u503c\u548c\u6700\u5c0f\u503c\u5b58\u5728\u4e92\u6362\u73b0\u8c61\uff0c\u56e0\u6b64\u9700\u8981\u540c\u65f6\u7ef4\u62a4\u6700\u5c0f\u503c\uff1a<code>min_result[i]=min(nums[i],min_result[i-1]*nums[i])<\/code><\/li>\n<li>\u5f53<code>nums[i]<\/code>\u4e3a\u8d1f\u6570\u65f6\uff0c\u9700\u8981\u5c06<code>max_result<\/code>\u548c<code>min_result<\/code>\u8fdb\u884c\u4e92\u6362\u540e\uff0c\u8fdb\u884c\u4e0b\u4e00\u6b65\u8ba1\u7b97\u3002<\/li>\n<\/ol>\n<h4>\u590d\u6742\u5ea6\u5206\u6790<\/h4>\n<ul>\n<li>\u65f6\u95f4\u590d\u6742\u5ea6\uff1aO\uff08n\uff09<\/li>\n<li>\u7a7a\u95f4\u590d\u6742\u5ea6\uff1aO\uff08n\uff09<\/li>\n<\/ul>\n<h4>\u89e3\u9898\u4ee3\u7801<\/h4>\n<pre><code class=\"language-python\">class Solution:\n    def maxProduct(self, nums: List[int]) -&gt; int:\n        if not nums:\n            return 0\n\n        n=len(nums)\n        max_result=[0]*n\n        min_result=[0]*n\n        max_result[0]=min_result[0]=result=nums[0]\n\n        for i in range(1,n):\n            if nums[i]&lt;0:\n                max_result,min_result=min_result,max_result\n\n            max_result[i]=max(nums[i],max_result[i-1]*nums[i])\n            min_result[i]=min(nums[i],min_result[i-1]*nums[i])\n            result=max(result,max_result[i])\n\n        return result<\/code><\/pre>\n<h3>Leecode 239. \u6ed1\u52a8\u7a97\u53e3\u6700\u5927\u503c<\/h3>\n<h4>\u9898\u76ee\u63cf\u8ff0<\/h4>\n<p>\u9898\u76ee\u94fe\u63a5\uff1a<a href=\"https:\/\/leetcode.cn\/problems\/sliding-window-maximum\/description\/\" target=\"_blank\"  rel=\"nofollow\" >https:\/\/leetcode.cn\/problems\/sliding-window-maximum\/description\/<\/a><\/p>\n<p>\u7ed9\u4f60\u4e00\u4e2a\u6574\u6570\u6570\u7ec4<code>nums<\/code>\uff0c\u6709\u4e00\u4e2a\u5927\u5c0f\u4e3a<code>k<\/code>\u7684\u6ed1\u52a8\u7a97\u53e3\u4ece\u6570\u7ec4\u7684\u6700\u5de6\u4fa7\u79fb\u52a8\u5230\u6570\u7ec4\u7684\u6700\u53f3\u4fa7\u3002\u4f60\u53ea\u53ef\u4ee5\u770b\u5230\u5728\u6ed1\u52a8\u7a97\u53e3\u5185\u7684<code>k<\/code>\u4e2a\u6570\u5b57\u3002\u6ed1\u52a8\u7a97\u53e3\u6bcf\u6b21\u53ea\u5411\u53f3\u79fb\u52a8\u4e00\u4f4d\u3002<\/p>\n<p>\u8fd4\u56de\u6ed1\u52a8\u7a97\u53e3\u4e2d\u7684\u6700\u5927\u503c \u3002<\/p>\n<p>\u793a\u4f8b1\uff1a<\/p>\n<blockquote>\n<p>\u8f93\u5165\uff1anums=[1,3,-1,-3,5,3,6,7],k=3<br \/>\n\u8f93\u51fa\uff1a[3,3,5,5,6,7]<\/p>\n<\/blockquote>\n<h4>\u89e3\u9898\u601d\u8def<\/h4>\n<p>\u53ef\u4ee5\u4f7f\u7528\u53cc\u5411\u961f\u5217\u6765\u89e3\u51b3\u6ed1\u52a8\u7a97\u53e3\u6700\u5927\u503c\u7684\u95ee\u9898\uff1a<\/p>\n<ul>\n<li>\u904d\u5386\u6570\u7ec4\uff0c\u5c06\u6570\u7ec4\u4e0b\u6807\u5b58\u653e\u5728\u53cc\u5411\u961f\u5217\u4e2d\uff0c\u4f7f\u7528<code>R=i<\/code>,<code>L=k-R<\/code>\u6807\u8bb0\u7a97\u53e3\u7684\u5de6\u8fb9\u754c\u548c\u53f3\u8fb9\u754c<\/li>\n<li>\u5f53\u6ed1\u52a8\u7a97\u53e3\u79fb\u52a8\u65f6\uff0c\u5f39\u51fa\u5de6\u8fb9\u754c\u5bf9\u5e94\u7684\u503c<\/li>\n<li>\u5982\u679c\u5f53\u524d\u904d\u5386\u7684\u6570\u6bd4\u961f\u5c3e\u7684\u503c\u5927\uff0c\u5219\u9700\u8981\u5f39\u51fa\u961f\u5c3e\u503c\uff0c\u76f4\u5230\u961f\u5217\u91cd\u65b0\u6ee1\u8db3\u4ece\u5927\u5230\u5c0f\u7684\u6392\u5e8f\u89c4\u5219<\/li>\n<li>\u521a\u5f00\u59cb\u904d\u5386\u65f6\uff0cL\u548cR\u90fd\u4e3a0\uff0c\u9700\u8981\u4e00\u4e2a\u5f62\u6210\u7a97\u53e3\u7684\u8fc7\u7a0b\uff0c\u6b64\u65f6\u6ca1\u6709\u6700\u5927\u503c\u8f93\u51fa\uff0cL\u4e0d\u52a8\uff0cR\u5411\u53f3\u79fb\u52a8<\/li>\n<li>\u5f53\u524d\u7a97\u53e3\u7684\u6700\u5927\u503c\u5373\u4e3a\u961f\u9996\u7684\u6570<\/li>\n<\/ul>\n<h4>\u590d\u6742\u5ea6\u5206\u6790<\/h4>\n<ul>\n<li>\u65f6\u95f4\u590d\u6742\u5ea6\uff1aO\uff08nlogn\uff09\uff0c\u5c06\u4e00\u4e2a\u5143\u7d20\u653e\u5165\u4f18\u5148\u961f\u5217\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO\uff08logn\uff09<\/li>\n<li>\u7a7a\u95f4\u590d\u6742\u5ea6\uff1aO\uff08n\uff09\uff0c\u5373\u4e3a\u4f18\u5148\u961f\u5217\u6240\u9700\u8981\u4f7f\u7528\u7684\u7a7a\u95f4<\/li>\n<\/ul>\n<h4>\u89e3\u9898\u4ee3\u7801<\/h4>\n<pre><code class=\"language-python\">class Solution:\n    def maxSlidingWindow(self, nums: List[int], k: int) -&gt; List[int]:\n        n=len(nums)\n        result=[]\n        #\u53cc\u7aef\u961f\u5217\uff0c\u5b58\u50a8\u5f53\u524d\u7a97\u53e3\u7684\u5143\u7d20\u7d22\u5f15\n        window=deque()\n\n        for i in range(n):\n            #\u5f53\u524d\u5143\u7d20\u8d85\u51fa\u7a97\u53e3\u8303\u56f4\uff0c\u79fb\u9664\u961f\u5217\u5de6\u7aef\u5143\u7d20\n            if window and window[0]&lt;=i-k:\n                window.popleft()\n\n            #\u4fdd\u6301\u7a97\u53e3\u961f\u5217\u4e2d\u5143\u7d20\u6309\u7167\u4ece\u5927\u5230\u5c0f\u7684\u987a\u5e8f\u6392\u5217\n            while window and nums[i]&gt;=nums[window[-1]]:\n                window.pop()\n            #\u5c06\u5f53\u524d\u5143\u7d20\u7684\u7d22\u5f15\u6dfb\u52a0\u5230\u7a97\u53e3\u961f\u5217\u7684\u53f3\u7aef\n            window.append(i)\n            #\u5f53\u7a97\u53e3\u957f\u5ea6\u8fbe\u5230k\u65f6\uff0c\u5c06\u7a97\u53e3\u4e2d\u6700\u5927\u503c\u6dfb\u52a0\u5230\u7ed3\u679c\u6570\u7ec4\u4e2d\n            if i&gt;=k-1:\n                result.append(nums[window[0]])\n        return result <\/code><\/pre>\n<h3>Leecode605. \u79cd\u82b1\u95ee\u9898<\/h3>\n<p>\u9898\u76ee\u94fe\u63a5\uff1a<a href=\"https:\/\/leetcode.cn\/problems\/can-place-flowers\/description\/\" target=\"_blank\"  rel=\"nofollow\" >https:\/\/leetcode.cn\/problems\/can-place-flowers\/description\/<\/a><\/p>\n<p>\u5047\u8bbe\u6709\u4e00\u4e2a\u5f88\u957f\u7684\u82b1\u575b\uff0c\u4e00\u90e8\u5206\u5730\u5757\u79cd\u690d\u4e86\u82b1\uff0c\u53e6\u4e00\u90e8\u5206\u5374\u6ca1\u6709\u3002\u53ef\u662f\uff0c\u82b1\u4e0d\u80fd\u79cd\u690d\u5728\u76f8\u90bb\u7684\u5730\u5757\u4e0a\uff0c\u5b83\u4eec\u4f1a\u4e89\u593a\u6c34\u6e90\uff0c\u4e24\u8005\u90fd\u4f1a\u6b7b\u53bb\u3002<\/p>\n<p>\u7ed9\u4f60\u4e00\u4e2a\u6574\u6570\u6570\u7ec4<code>flowerbed<\/code>\u8868\u793a\u82b1\u575b\uff0c\u7531\u82e5\u5e72<code>0<\/code>\u548c<code>1<\/code>\u7ec4\u6210\uff0c\u5176\u4e2d<code>0 <\/code>\u8868\u793a\u6ca1\u79cd\u690d\u82b1\uff0c<code>1<\/code>\u8868\u793a\u79cd\u690d\u4e86\u82b1\u3002\u53e6\u6709\u4e00\u4e2a\u6570<code>n<\/code>\uff0c\u80fd\u5426\u5728\u4e0d\u6253\u7834\u79cd\u690d\u89c4\u5219\u7684\u60c5\u51b5\u4e0b\u79cd\u5165<code>n<\/code>\u6735\u82b1\uff1f\u80fd\u5219\u8fd4\u56de true \uff0c\u4e0d\u80fd\u5219\u8fd4\u56de false \u3002<\/p>\n<blockquote>\n<p>\u793a\u4f8b\uff1a<br \/>\n\u8f93\u5165\uff1aflowerbed=[1,0,0,0,1]\uff0cn=1<br \/>\n\u8f93\u51fa\uff1a true<\/p>\n<\/blockquote>\n<h4>\u89e3\u9898\u601d\u8def<\/h4>\n<p>\u53ef\u4ee5\u4f7f\u7528\u52a8\u6001\u89c4\u5212\u6c42\u89e3\uff0c\u5b9a\u4e49dp[i]\u4e3a\u957f\u5ea6\u4e3ai\u7684\u82b1\u575b\u7684\u89e3\uff0c\u5219\u89c4\u6a21\u7f29\u5c0f\u8fc7\u7a0b\u5982\u4e0b\uff1a<\/p>\n<ul>\n<li>\u5bf9\u4e8e\u7b2ci\u4e2a\u4f4d\u7f6e\uff0ci\u53ef\u4ee5\u79cd\u5219i-1\u4e0d\u53ef\u4ee5\u79cd\uff0c\u95ee\u9898\u89c4\u6a21\u7f29\u5c0f\u5230i-2<\/li>\n<li>i\u4e0d\u79cd\u7684\u8bdd\uff0c\u95ee\u9898\u89c4\u6a21\u7f29\u5c0f\u5230i-1<\/li>\n<li>\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\uff1a\n<ul>\n<li>i\u4e0d\u79cd\u65f6\uff1adp[i]=dp[i-1]<\/li>\n<li>i\u79cd\u65f6\uff1adp[i]=dp[i-2]+1<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<h4>\u590d\u6742\u5ea6\u5206\u6790<\/h4>\n<ul>\n<li>\u65f6\u95f4\u590d\u6742\u5ea6\uff1aO\uff08n\uff09<\/li>\n<li>\u7a7a\u95f4\u590d\u6742\u5ea6\uff1aO\uff08n\uff09<\/li>\n<\/ul>\n<h4>\u89e3\u9898\u4ee3\u7801\uff1a<\/h4>\n<pre><code class=\"language-python\">class Solution:\n    def canPlaceFlowers(self, flowerbed: List[int], n: int) -&gt; bool:\n        if n==0:\n            return  True\n\n        flowerbed=[0]+flowerbed+[0]\n\n        dp=[0 for _ in range(len(flowerbed))]\n\n        for i in range(1,len(flowerbed)-1):\n            if flowerbed[i-1]==flowerbed[i]==flowerbed[i+1]==0:\n                dp[i]=dp[i-2]+1\n            else:\n                dp[i]=dp[i-1]\n\n            if dp[i]==n:\n                return True\n\n        return False\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>LeeCode.135 \u5206\u53d1\u7cd6\u679c \u9898\u76ee\u63cf\u8ff0 \u9898\u76ee\u94fe\u63a5\uff1ahttps:\/\/leetcode.cn\/problems\/candy\/?en &#8230;<\/p>\n","protected":false},"author":1,"featured_media":231,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"emotion":"","emotion_color":"","title_style":"","license":"","footnotes":""},"categories":[23,2],"tags":[25,29,28],"class_list":["post-182","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-leecode","category-algorithm_learning","tag-leecode","tag-29","tag-28"],"_links":{"self":[{"href":"https:\/\/lingbo.online\/index.php\/wp-json\/wp\/v2\/posts\/182","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lingbo.online\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/lingbo.online\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/lingbo.online\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/lingbo.online\/index.php\/wp-json\/wp\/v2\/comments?post=182"}],"version-history":[{"count":10,"href":"https:\/\/lingbo.online\/index.php\/wp-json\/wp\/v2\/posts\/182\/revisions"}],"predecessor-version":[{"id":372,"href":"https:\/\/lingbo.online\/index.php\/wp-json\/wp\/v2\/posts\/182\/revisions\/372"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/lingbo.online\/index.php\/wp-json\/wp\/v2\/media\/231"}],"wp:attachment":[{"href":"https:\/\/lingbo.online\/index.php\/wp-json\/wp\/v2\/media?parent=182"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lingbo.online\/index.php\/wp-json\/wp\/v2\/categories?post=182"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lingbo.online\/index.php\/wp-json\/wp\/v2\/tags?post=182"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}