{"id":1006,"date":"2021-03-12T17:14:24","date_gmt":"2021-03-12T09:14:24","guid":{"rendered":"http:\/\/www.zyhcoding.club\/?p=1006"},"modified":"2021-03-12T17:40:51","modified_gmt":"2021-03-12T09:40:51","slug":"%e5%8d%95%e8%b0%83%e6%a0%88","status":"publish","type":"post","link":"http:\/\/www.zyhcoding.club\/index.php\/2021\/03\/12\/%e5%8d%95%e8%b0%83%e6%a0%88\/","title":{"rendered":"\u5355\u8c03\u6808"},"content":{"rendered":"

\u5355\u8c03\u6808<\/h4>\n

\u987e\u540d\u601d\u4e49\uff0c\u5355\u8c03\u6808\u5c31\u662f\u6307\u5b58\u653e\u6709\u5e8f\u6570\u636e\u7684\u6808\uff0c\u5206\u4e3a\u5355\u8c03\u9012\u589e\u6808\u548c\u5355\u8c03\u9012\u51cf\u6808\u3002<\/p>\n

\n

\u5355\u8c03\u9012\u589e\u6808\uff1a\u6808\u5185\u6570\u636e\u4ece\u6808\u5e95\u5230\u6808\u9876\u9012\u589e
\n\u5355\u8c03\u9012\u51cf\u6808\uff1a\u7ad9\u5185\u6570\u636e\u4ece\u6808\u5e95\u5230\u6808\u9876\u9012\u51cf<\/p>\n<\/blockquote>\n

\u5355\u8c03\u6808\u7684\u4f5c\u7528\uff1a\u53ef\u4ee5\u4ee5O(1)<\/code><\/code>\u7684\u5e73\u5747\u65f6\u95f4\u590d\u6742\u5ea6\u4e00\u5217\u6570\u4e2d\uff0c\u6bcf\u4e2a\u6570\u7684\u5de6\u53f3\u4e24\u8fb9\u6bd4\u5b83\u5c0f\u7684\u7b2c\u4e00\u4e2a\u6570\u7684\u4f4d\u7f6e\u3002<\/p>\n

\u67f1\u72b6\u56fe\u4e2d\u6700\u5927\u7684\u77e9\u5f62<\/a><\/h5>\n

\u7ed9\u4e00\u5217\u6709\u9ad8\u5ea6\u7684\u67f1\u5f62\uff0c\u6c42\u5176\u4e2d\u9762\u79ef\u6700\u5927\u7684\u77e9\u5f62\u3002
\n\"\"<\/p>\n

\u8003\u8651\u679a\u4e3e\u6709\u6548\u9ad8\u5ea6\uff0c\u5f53\u6bcf\u4e2a\u67f1\u5f62\u505a\u4e3a\u6709\u6548\u9ad8\u5ea6\u67f1\u5f62\u6765\u8ba1\u7b97\uff0c\u5373\u5f53\u524d\u67f1\u5f62\u5411\u5de6\u4e00\u76f4\u884d\u751f\u81f3\u6bd4\u5b83\u4f4e\u7684\u7b2c\u4e00\u4e2a\u67f1\u5f62\uff0c\u5411\u53f3\u4e5f\u662f\uff0c\u7136\u540e\u8fd9\u4e2a\u957f\u5ea6\u8bda\u610f\u67f1\u5f62\u7684\u9ad8\u5ea6\u5c31\u662f\u5f53\u524d\u67f1\u5f62\u4e3a\u6709\u6548\u9ad8\u5ea6\u65f6\u7684\u6700\u5927\u77e9\u5f62\u3002
\n\u53ef\u5229\u7528\u5355\u8c03\u6808\u6c42\u6bcf\u4e2a\u67f1\u5f62\u5411\u5de6\u5411\u53f3\u7b2c\u4e00\u4e2a\u6bd4\u5b83\u4f4e\u7684\u77e9\u5f62\u4f4d\u7f6e\u3002<\/p>\n

\u5728\u4e0a\u56fe\u4e2d\uff0c\u53ef\u5148\u628a2\u5165\u6808\uff0c\u7136\u540e\u626b\u63cf\u52301\u65f6\uff0c1\u6bd4\u6808\u9876\u5143\u7d202\u5c0f\uff0c\u52192\u5411\u53f3\u884d\u751f\u7684\u67f1\u5f62\u6700\u591a\u4e3a1\u4e2a\uff0c\u5c31\u662f\u5b83\u81ea\u5df1\u3002\u7136\u540e5\uff0c6\u5747\u5982\u6808\uff0c\u56e0\u4e3a\u90fd\u6bd41\u5927\uff0c\u6240\u4ee51\u4ecd\u7136\u80fd\u591f\u5411\u53f3\u7ee7\u7eed\u884d\u751f\u3002\u63a5\u7740\u5230\u4e862\uff0c5\u548c6\u5747\u8981\u51fa\u6808\uff0c6\u53ef\u884d\u751f\u81f32\uff0c5\u4e5f\u662f\u884d\u751f\u81f32\uff0c2\u5982\u6808\uff0c1\u53ef\u4ee5\u7ee7\u7eed\u5411\u53f3\u884d\u751f...<\/p>\n

\u4f7f\u7528\u4e0a\u8ff0\u65b9\u6cd5\u53ef\u4ee5\u770b\u51fa\u5355\u8c03\u6808\u53ef\u4ee5\u4ee5O(n)<\/code><\/code>\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u6c42\u51fa\u6bcf\u4e2a\u67f1\u5f62\u5411\u4e24\u8fb9\u884d\u751f\u7684\u6700\u5927\u957f\u5ea6\u3002<\/p>\n

class Solution {\npublic:\n    int largestRectangleArea(vector<int>& heights) {\n        stack<int> st1, st2;\n        int n = heights.size();\n        if (0==n)   return 0;\n        vector<int> dp1(n), dp2(n);\n        int ans = 0;\n        for (int i=0; i<n; i++){\n            while (!st1.empty() && st1.top()>heights[i]){\n                dp2[st2.top()] = i-st2.top();\n                st1.pop();  st2.pop();\n            }\n            st1.push(heights[i]);\n            st2.push(i);\n        }\n        while (!st1.empty()){\n            dp2[st2.top()] = n-st2.top();\n            st1.pop();  st2.pop();\n        }\n        for (int i=n-1; i>=0; i--){\n            while (!st1.empty() && st1.top()>heights[i]){\n                dp1[st2.top()] = st2.top()-i;\n                st1.pop();  st2.pop();\n            }\n            st1.push(heights[i]);\n            st2.push(i);\n        }\n        while (!st1.empty()){\n            dp1[st2.top()] = st2.top()+1;\n            st1.pop();  st2.pop();\n        }\n        for (int i=0; i<n; i++) ans = max(ans, heights[i]*(dp1[i]+dp2[i]-1));\n        return ans;\n    }\n};<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u5355\u8c03\u6808 \u987e\u540d\u601d\u4e49\uff0c\u5355\u8c03\u6808\u5c31\u662f\u6307\u5b58\u653e\u6709\u5e8f\u6570\u636e\u7684\u6808\uff0c\u5206\u4e3a\u5355\u8c03\u9012\u589e\u6808\u548c\u5355\u8c03\u9012\u51cf\u6808\u3002 \u5355\u8c03\u9012\u589e\u6808\uff1a\u6808\u5185\u6570\u636e\u4ece […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[14],"tags":[],"_links":{"self":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/1006"}],"collection":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/comments?post=1006"}],"version-history":[{"count":4,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/1006\/revisions"}],"predecessor-version":[{"id":1009,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/1006\/revisions\/1009"}],"wp:attachment":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/media?parent=1006"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/categories?post=1006"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/tags?post=1006"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}