{"id":174,"date":"2025-08-26T11:52:58","date_gmt":"2025-08-26T03:52:58","guid":{"rendered":"https:\/\/heyingnian.com\/?p=174"},"modified":"2025-08-26T15:44:52","modified_gmt":"2025-08-26T07:44:52","slug":"leetcode-239","status":"publish","type":"post","link":"https:\/\/heyingnian.com\/index.php\/2025\/08\/26\/leetcode-239\/","title":{"rendered":"\u6ed1\u52a8\u7a97\u53e3\u6700\u5927\u503c"},"content":{"rendered":"\n<h1 class=\"wp-block-heading\"><br>\ud83d\udd17 \u6ed1\u52a8\u7a97\u53e3\u6700\u5927\u503c<\/h1>\n\n\n\n<p>\u9898\u76ee\u6765\u6e90\uff1a<a target=\"_blank\" rel=\"noreferrer noopener\"><\/a><a href=\"https:\/\/leetcode.cn\/problems\/sliding-window-maximum\/?envType=study-plan-v2&amp;envId=top-100-liked\" target=\"_blank\" rel=\"noopener\">239. \u6ed1\u52a8\u7a97\u53e3\u6700\u5927\u503c &#8211; \u529b\u6263\uff08LeetCode\uff09<\/a><\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p>\ud83d\udccc \u9898\u76ee\u63cf\u8ff0<\/p>\n\n\n\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\u6700\u53f3\u4fa7\u3002\u4f60\u53ea\u80fd\u770b\u5230\u7a97\u53e3\u5185\u7684 <code>k<\/code> \u4e2a\u6570\u5b57\u3002\u6ed1\u52a8\u7a97\u53e3\u6bcf\u6b21\u5411\u53f3\u79fb\u52a8\u4e00\u4f4d\u3002<\/p>\n\n\n\n<p>\u8fd4\u56de<strong>\u6bcf\u4e2a\u6ed1\u52a8\u7a97\u53e3\u4e2d\u7684\u6700\u5927\u503c<\/strong>\u7ec4\u6210\u7684\u6570\u7ec4\u3002<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p>\u2705 \u793a\u4f8b\u89e3\u6790<\/p>\n\n\n\n<p>\u793a\u4f8b 1\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u8f93\u5165\uff1a<code>nums = [1,3,-1,-3,5,3,6,7]<\/code>,&nbsp;<code>k = 3<\/code><\/li>\n\n\n\n<li>\u8f93\u51fa\uff1a<code>[3,3,5,5,6,7]<\/code><\/li>\n\n\n\n<li>\u89e3\u91ca\uff1a\n<ul class=\"wp-block-list\">\n<li>\u7a97\u53e3&nbsp;<code>[1,3,-1]<\/code>&nbsp;\u2192 \u6700\u5927\u503c&nbsp;<code>3<\/code><\/li>\n\n\n\n<li>\u7a97\u53e3&nbsp;<code>[3,-1,-3]<\/code>&nbsp;\u2192 \u6700\u5927\u503c&nbsp;<code>3<\/code><\/li>\n\n\n\n<li>\u7a97\u53e3&nbsp;<code>[-1,-3,5]<\/code>&nbsp;\u2192 \u6700\u5927\u503c&nbsp;<code>5<\/code><\/li>\n\n\n\n<li>\u7a97\u53e3&nbsp;<code>[-3,5,3]<\/code>&nbsp;\u2192 \u6700\u5927\u503c&nbsp;<code>5<\/code><\/li>\n\n\n\n<li>\u7a97\u53e3&nbsp;<code>[5,3,6]<\/code>&nbsp;\u2192 \u6700\u5927\u503c&nbsp;<code>6<\/code><\/li>\n\n\n\n<li>\u7a97\u53e3&nbsp;<code>[3,6,7]<\/code>&nbsp;\u2192 \u6700\u5927\u503c&nbsp;<code>7<\/code><\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<p>\u793a\u4f8b 2\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u8f93\u5165\uff1a<code>nums = [1]<\/code>,&nbsp;<code>k = 1<\/code><\/li>\n\n\n\n<li>\u8f93\u51fa\uff1a<code>[1]<\/code><\/li>\n\n\n\n<li>\u89e3\u91ca\uff1a\u53ea\u6709\u4e00\u4e2a\u5143\u7d20\uff0c\u6700\u5927\u503c\u5c31\u662f\u5b83\u672c\u8eab\u3002<\/li>\n<\/ul>\n\n\n\n<p>\u793a\u4f8b 3\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u8f93\u5165\uff1a<code>nums = [1,-1]<\/code>,&nbsp;<code>k = 1<\/code><\/li>\n\n\n\n<li>\u8f93\u51fa\uff1a<code>[1, -1]<\/code><\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p>\u26a0\ufe0f \u63d0\u793a<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>1 &lt;= nums.length &lt;= 10\u2075<\/code><\/li>\n\n\n\n<li><code>-10\u2074 &lt;= nums[i] &lt;= 10\u2074<\/code><\/li>\n\n\n\n<li><code>1 &lt;= k &lt;= nums.length<\/code><\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p>\ud83d\udca1 \u89e3\u6cd5\uff1a\u5355\u8c03\u961f\u5217\uff08\u53cc\u7aef\u961f\u5217\uff09\u2014\u2014 O(n) \u65f6\u95f4\uff0cO(k) \u7a7a\u95f4<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code><strong>class<\/strong> <strong>Solution<\/strong> {\n    <strong>public<\/strong> <strong>int<\/strong>&#91;] maxSlidingWindow(<strong>int<\/strong>&#91;] nums, <strong>int<\/strong> k) {\n        <strong>int<\/strong> length = nums.length;\n        <strong>int<\/strong>&#91;] ans = <strong>new<\/strong> <strong>int<\/strong>&#91;length - k + 1];\n        Deque&lt;Integer> deque = <strong>new<\/strong> LinkedList&lt;>();\n        <strong>for<\/strong> (<strong>int<\/strong> i = 0; i &lt; length; i++) {\n            <strong>while<\/strong> (!deque.isEmpty() &amp;&amp; deque.peekFirst() &lt; i - k + 1) {\n                deque.pollFirst();\n            }\n            <strong>while<\/strong> (!deque.isEmpty() &amp;&amp; nums&#91;i] > nums&#91;deque.peekLast()]) {\n                deque.pollLast();\n            }\n            deque.addLast(i);\n            <strong>if<\/strong> (i >= k - 1) {\n                ans&#91;i - k + 1] = nums&#91;deque.peekFirst()];\n            }\n        }\n        <strong>return<\/strong> ans;\n    }\n}<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p>\ud83d\udcca \u590d\u6742\u5ea6\u5206\u6790<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>\u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(n)<\/strong><br>\u6bcf\u4e2a\u5143\u7d20\u6700\u591a\u5165\u961f\u548c\u51fa\u961f\u4e00\u6b21\uff0c\u6574\u4f53\u904d\u5386\u4e3a\u7ebf\u6027\u65f6\u95f4\u3002<\/li>\n\n\n\n<li><strong>\u7a7a\u95f4\u590d\u6742\u5ea6\uff1aO(k)<\/strong><br>\u53cc\u7aef\u961f\u5217\u4e2d\u6700\u591a\u5b58\u50a8 <code>k<\/code> \u4e2a\u7d22\u5f15\uff08\u7a97\u53e3\u5927\u5c0f\uff09\uff0c\u56e0\u6b64\u7a7a\u95f4\u590d\u6742\u5ea6\u4e3a O(k)\u3002<br>\u8fd4\u56de\u6570\u7ec4\u4e0d\u8ba1\u5165\u989d\u5916\u7a7a\u95f4\u3002<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p>\ud83e\udde9 \u89e3\u9898\u601d\u8def<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>\u6838\u5fc3\u6311\u6218<\/strong>\uff1a<br>\u66b4\u529b\u89e3\u6cd5\uff08\u5bf9\u6bcf\u4e2a\u7a97\u53e3\u904d\u5386 <code>k<\/code> \u4e2a\u5143\u7d20\u627e\u6700\u5927\u503c\uff09\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a O(nk)\uff0c\u5728 <code>n<\/code> \u8f83\u5927\u65f6\u4f1a\u8d85\u65f6\u3002<br>\u9700\u8981\u4e00\u79cd<strong>\u52a8\u6001\u7ef4\u62a4\u7a97\u53e3\u6700\u5927\u503c<\/strong>\u7684\u6570\u636e\u7ed3\u6784\u3002<\/li>\n\n\n\n<li><strong>\u5355\u8c03\u961f\u5217\u601d\u60f3<\/strong>\uff1a<br>\u4f7f\u7528\u4e00\u4e2a<strong>\u53cc\u7aef\u961f\u5217\uff08Deque\uff09<\/strong>\uff0c\u5b58\u50a8\u6570\u7ec4<strong>\u7d22\u5f15<\/strong>\uff0c\u5e76\u7ef4\u62a4\u961f\u5217\u4e2d\u5bf9\u5e94\u503c\u7684<strong>\u5355\u8c03\u9012\u51cf\u6027<\/strong>\u3002\n<ul class=\"wp-block-list\">\n<li>\u961f\u9996\u59cb\u7ec8\u662f\u5f53\u524d\u7a97\u53e3\u4e2d\u6700\u5927\u503c\u7684\u7d22\u5f15\u3002<\/li>\n\n\n\n<li>\u961f\u5217\u4e2d\u53ea\u4fdd\u7559\u201c\u53ef\u80fd\u6210\u4e3a\u672a\u6765\u6700\u5927\u503c\u201d\u7684\u5143\u7d20\u3002<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>\u7ef4\u62a4\u5355\u8c03\u6027<\/strong>\uff1a\n<ul class=\"wp-block-list\">\n<li><strong>\u6b65\u9aa4 1\uff1a\u79fb\u9664\u8fc7\u671f\u5143\u7d20<\/strong><br>\u82e5\u961f\u9996\u7d22\u5f15\u5df2\u4e0d\u5728\u5f53\u524d\u7a97\u53e3\u5185\uff08<code>&lt; i - k + 1<\/code>\uff09\uff0c\u5c06\u5176\u4ece\u961f\u9996\u79fb\u9664\u3002<\/li>\n\n\n\n<li><strong>\u6b65\u9aa4 2\uff1a\u7ef4\u62a4\u9012\u51cf\u6027<\/strong><br>\u82e5\u5f53\u524d\u5143\u7d20&nbsp;<code>nums[i]<\/code>&nbsp;\u5927\u4e8e\u961f\u5c3e\u5bf9\u5e94\u503c\uff0c\u5219\u4e0d\u65ad\u4ece\u961f\u5c3e\u5f39\u51fa\uff0c\u76f4\u5230\u961f\u5217\u4e3a\u7a7a\u6216\u961f\u5c3e\u503c\u66f4\u5927\u3002<br>\u8fd9\u6837\u53ef\u4ee5\u201c\u6dd8\u6c70\u201d\u6389\u90a3\u4e9b\u6bd4\u5f53\u524d\u5143\u7d20\u5c0f\u4e14\u4f4d\u7f6e\u66f4\u9760\u524d\u7684\u6570\u2014\u2014\u5b83\u4eec\u4e0d\u53ef\u80fd\u518d\u6210\u4e3a\u6700\u5927\u503c\u3002<\/li>\n\n\n\n<li><strong>\u6b65\u9aa4 3\uff1a\u5f53\u524d\u7d22\u5f15\u5165\u961f<\/strong><br>\u5c06\u5f53\u524d\u7d22\u5f15&nbsp;<code>i<\/code>&nbsp;\u52a0\u5165\u961f\u5c3e\u3002<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>\u83b7\u53d6\u6700\u5927\u503c<\/strong>\uff1a<br>\u5f53 <code>i &gt;= k - 1<\/code> \u65f6\uff0c\u8bf4\u660e\u7a97\u53e3\u5df2\u5f62\u6210\uff0c\u6b64\u65f6\u961f\u9996\u5143\u7d20\u5373\u4e3a\u5f53\u524d\u7a97\u53e3\u6700\u5927\u503c\u7684\u7d22\u5f15\uff0c<code>nums[deque.peekFirst()]<\/code> \u5373\u4e3a\u6240\u6c42\u3002<\/li>\n\n\n\n<li><strong>\u4e3e\u4f8b\u8bf4\u660e<\/strong>\uff1a<br>\u5bf9\u4e8e <code>nums = [1,3,-1], k = 3<\/code>\uff1a\n<ul class=\"wp-block-list\">\n<li>i=0: \u961f\u5217\u4e3a\u7a7a \u2192 \u52a0\u5165\u7d22\u5f15&nbsp;<code>0<\/code>&nbsp;\u2192 deque=[0]<\/li>\n\n\n\n<li>i=1:&nbsp;<code>3 &gt; 1<\/code>&nbsp;\u2192 \u5f39\u51fa&nbsp;<code>0<\/code>\uff0c\u52a0\u5165&nbsp;<code>1<\/code>&nbsp;\u2192 deque=[1]<\/li>\n\n\n\n<li>i=2:&nbsp;<code>-1 &lt; 3<\/code>&nbsp;\u2192 \u76f4\u63a5\u52a0\u5165&nbsp;<code>2<\/code>&nbsp;\u2192 deque=[1,2]<br>\u6b64\u65f6&nbsp;<code>i=2 &gt;= 2<\/code>\uff0c\u53d6\u961f\u9996&nbsp;<code>nums[1]=3<\/code>&nbsp;\u2192 \u6700\u5927\u503c\u4e3a&nbsp;<code>3<\/code><\/li>\n<\/ul>\n<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>\ud83d\udd17 \u6ed1\u52a8\u7a97\u53e3\u6700\u5927\u503c \u9898\u76ee\u6765\u6e90\uff1a239. \u6ed1\u52a8\u7a97\u53e3\u6700\u5927\u503c &#8211; \u529b\u6263\uff08LeetCode\uff09 \ud83d\udccc \u9898\u76ee\u63cf\u8ff0 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[27,12],"tags":[28,24,14],"class_list":["post-174","post","type-post","status-publish","format-standard","hentry","category-substrings","category-algorithm","tag-deque","tag-sliding_window","tag-algorithm"],"_links":{"self":[{"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/posts\/174","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/comments?post=174"}],"version-history":[{"count":2,"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/posts\/174\/revisions"}],"predecessor-version":[{"id":178,"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/posts\/174\/revisions\/178"}],"wp:attachment":[{"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/media?parent=174"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/categories?post=174"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/heyingnian.com\/index.php\/wp-json\/wp\/v2\/tags?post=174"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}