{"id":1650,"date":"2018-01-24T21:17:37","date_gmt":"2018-01-25T05:17:37","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1650"},"modified":"2018-09-03T22:30:07","modified_gmt":"2018-09-04T05:30:07","slug":"leetcode-239-sliding-window-maximum","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/heap\/leetcode-239-sliding-window-maximum\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 239. Sliding Window Maximum"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 239. Sliding Window Maximum - \u5237\u9898\u627e\u5de5\u4f5c EP159\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/2SXqBsTR6a8?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e2a\u6570\u7ec4\uff0c\u8ba9\u4f60\u8f93\u51fa\u79fb\u52a8\u7a97\u53e3\u7684\u6700\u5927\u503c\u3002<\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p><a href=\"https:\/\/leetcode.com\/problems\/sliding-window-maximum\/\">https:\/\/leetcode.com\/problems\/sliding-window-maximum\/<\/a><\/p>\n<p>Given an array\u00a0<i>nums<\/i>, there is a sliding window of size\u00a0<i>k<\/i>\u00a0which is moving from the very left of the array to the very right. You can only see the\u00a0<i>k<\/i>\u00a0numbers in the window. Each time the sliding window moves right by one position.<\/p>\n<p>For example,<br \/>\nGiven\u00a0<i>nums<\/i>\u00a0=\u00a0<code>[1,3,-1,-3,5,3,6,7]<\/code>, and\u00a0<i>k<\/i>\u00a0= 3.<\/p>\n<pre>Window position                Max\r\n---------------               -----\r\n[1  3  -1] -3  5  3  6  7       3\r\n 1 [3  -1  -3] 5  3  6  7       3\r\n 1  3 [-1  -3  5] 3  6  7       5\r\n 1  3  -1 [-3  5  3] 6  7       5\r\n 1  3  -1  -3 [5  3  6] 7       6\r\n 1  3  -1  -3  5 [3  6  7]      7\r\n<\/pre>\n<p>Therefore, return the max sliding window as\u00a0<code>[3,3,5,5,6,7]<\/code>.<\/p>\n<p><b>Note:\u00a0<\/b><br \/>\nYou may assume\u00a0<i>k<\/i>\u00a0is always valid, ie: 1 \u2264 k \u2264 input array&#8217;s size for non-empty array.<\/p>\n<p><b>Follow up:<\/b><br \/>\nCould you solve it in linear time?<\/p>\n<p><ins class=\"adsbygoogle\" style=\"display: block; text-align: center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"7983117522\">\u00a0<\/ins><\/p>\n<p><strong>Idea:<\/strong><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1657\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/239-ep159.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/239-ep159.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/239-ep159-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/239-ep159-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1656\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/239-ep159-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/239-ep159-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/239-ep159-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/239-ep159-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p>&nbsp;<\/p>\n<h1><strong>Solution 1: Brute Force<\/strong><\/h1>\n<p>Time complexity: O((n &#8211; k + 1) * k)<\/p>\n<p>Space complexity: O(1)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 180 ms\r\nclass Solution {\r\npublic:\r\n  vector&lt;int&gt; maxSlidingWindow(vector&lt;int&gt;&amp; nums, int k) {    \r\n    vector&lt;int&gt; ans;\r\n    for (int i = k - 1; i &lt; nums.size(); ++i) {\r\n      ans.push_back(*max_element(nums.begin() + i - k + 1, nums.begin() + i + 1));\r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:java decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 80 ms\r\nclass Solution {\r\n  public int[] maxSlidingWindow(int[] nums, int k) {\r\n    if (k == 0) return new int[0];\r\n    \r\n    int[] ans = new int[nums.length - k + 1];    \r\n    for (int i = k - 1; i &lt; nums.length; ++i) {\r\n      int maxNum = nums[i];\r\n      for (int j = 1; j &lt; k; ++j)\r\n        if (nums[i - j] &gt; maxNum) maxNum = nums[i - j];\r\n      ans[i - k + 1] = maxNum;\r\n    }\r\n    return ans;\r\n  }\r\n}<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:python decode:true \">\"\"\"\r\nAuthor: Huahua\r\nRunning time: 1044 ms\r\n\"\"\"\r\nclass Solution:\r\n  def maxSlidingWindow(self, nums, k):\r\n    if not nums: return []    \r\n    return [max(nums[i:i+k]) for i in range(len(nums) - k + 1)]<\/pre>\n<\/div><\/div>\n<h1><strong>Solution 2: BST<\/strong><\/h1>\n<p>Time complexity: O((n &#8211; k + 1) * logk)<\/p>\n<p>Space complexity: O(k)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 82 ms\r\nclass Solution {\r\npublic:\r\n  vector&lt;int&gt; maxSlidingWindow(vector&lt;int&gt;&amp; nums, int k) {\r\n    vector&lt;int&gt; ans;\r\n    if (nums.empty()) return ans;\r\n    multiset&lt;int&gt; window(nums.begin(), nums.begin() + k - 1);\r\n    for (int i = k - 1; i &lt; nums.size(); ++i) {\r\n      window.insert(nums[i]);\r\n      ans.push_back(*window.rbegin());\r\n      if (i - k + 1 &gt;= 0)\r\n        window.erase(window.equal_range(nums[i - k + 1]).first);      \r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n<h1><strong>Solution 3: Monotonic Queue<\/strong><\/h1>\n<p>Time complexity: O(n)<\/p>\n<p>Space complexity: O(k)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 70 ms\r\nclass MonotonicQueue {\r\npublic:\r\n  void push(int e) {\r\n    while(!data_.empty() &amp;&amp; e &gt; data_.back()) data_.pop_back();\r\n    data_.push_back(e);\r\n  } \r\n  \r\n  void pop() {\r\n    data_.pop_front();\r\n  }\r\n  \r\n  int max() const { return data_.front(); }\r\nprivate:\r\n  deque&lt;int&gt; data_;\r\n};\r\n\r\nclass Solution {\r\npublic:\r\n  vector&lt;int&gt; maxSlidingWindow(vector&lt;int&gt;&amp; nums, int k) {\r\n    MonotonicQueue q;\r\n    vector&lt;int&gt; ans;\r\n        \r\n    for (int i = 0; i &lt; nums.size(); ++i) {\r\n      q.push(nums[i]);\r\n      if (i - k + 1 &gt;= 0) {\r\n        ans.push_back(q.max());\r\n        if (nums[i - k + 1] == q.max()) q.pop();\r\n      }      \r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">C++ V2<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 65 ms\r\nclass Solution {\r\npublic:\r\n  vector&lt;int&gt; maxSlidingWindow(vector&lt;int&gt;&amp; nums, int k) {\r\n    deque&lt;int&gt; index;\r\n    vector&lt;int&gt; ans;\r\n        \r\n    for (int i = 0; i &lt; nums.size(); ++i) {\r\n      while (!index.empty() &amp;&amp; nums[i] &gt;= nums[index.back()]) index.pop_back();\r\n      index.push_back(i);      \r\n      if (i - k + 1 &gt;= 0) ans.push_back(nums[index.front()]);\r\n      if (i - k + 1 &gt;= index.front()) index.pop_front();\r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">C++ V3<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 67 ms\r\nclass Solution {\r\npublic:\r\n  vector&lt;int&gt; maxSlidingWindow(vector&lt;int&gt;&amp; nums, int k) {\r\n    deque&lt;int&gt; q;\r\n    vector&lt;int&gt; ans;\r\n        \r\n    for (int i = 0; i &lt; nums.size(); ++i) {\r\n      while (!q.empty() &amp;&amp; nums[i] &gt; q.back()) q.pop_back();\r\n      q.push_back(nums[i]);\r\n      const int s = i - k + 1;\r\n      if (s &lt; 0) continue;      \r\n      ans.push_back(q.front());\r\n      if (nums[s] == q.front()) q.pop_front();\r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:java decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 19 ms\r\nclass Solution {\r\n  public int[] maxSlidingWindow(int[] nums, int k) {\r\n    if (k == 0) return nums;\r\n    \r\n    int[] ans = new int[nums.length - k + 1];\r\n    Deque&lt;Integer&gt; indices = new LinkedList&lt;&gt;();\r\n    \r\n    for (int i = 0; i &lt; nums.length; ++i) {\r\n      while (indices.size() &gt; 0 &amp;&amp; nums[i] &gt;= nums[indices.getLast()])\r\n        indices.removeLast();\r\n      \r\n      indices.addLast(i);\r\n      if (i - k + 1 &gt;= 0) ans[i - k + 1] = nums[indices.getFirst()];\r\n      if (i - k + 1 &gt;= indices.getFirst()) indices.removeFirst();\r\n    }\r\n             \r\n    return ans;\r\n  }\r\n}<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:python decode:true \">\"\"\"\r\nAuthor: Huahua\r\nRunning time: 238 ms\r\n\"\"\"\r\nclass MaxQueue:\r\n  def __init__(self):\r\n    self.q_ = collections.deque()\r\n  \r\n  def push(self, e):\r\n    while self.q_ and e &gt; self.q_[-1]: self.q_.pop()\r\n    self.q_.append(e)\r\n  \r\n  def pop(self):\r\n    self.q_.popleft()\r\n  \r\n  def max(self):\r\n    return self.q_[0]\r\n    \r\nclass Solution:\r\n  def maxSlidingWindow(self, nums, k):\r\n    q = MaxQueue()\r\n    ans = []\r\n    for i in range(len(nums)):\r\n      q.push(nums[i])\r\n      if i &gt;= k - 1: \r\n        ans.append(q.max())\r\n        if nums[i - k + 1] == q.max(): q.pop()\r\n    return ans<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3 V2<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:python decode:true\">\"\"\"\r\nAuthor: Huahua\r\nRunning time: 193 ms\r\n\"\"\"\r\nclass Solution:\r\n  def maxSlidingWindow(self, nums, k):\r\n    indices = collections.deque()\r\n    ans = []\r\n    for i in range(len(nums)):\r\n      while indices and nums[i] &gt;= nums[indices[-1]]: indices.pop()\r\n      indices.append(i)\r\n      if i &gt;= k - 1: ans.append(nums[indices[0]])\r\n      if i - k + 1 == indices[0]: indices.popleft()\r\n    return ans<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e2a\u6570\u7ec4\uff0c\u8ba9\u4f60\u8f93\u51fa\u79fb\u52a8\u7a97\u53e3\u7684\u6700\u5927\u503c\u3002 Problem: https:\/\/leetcode.com\/problems\/sliding-window-maximum\/ Given an array\u00a0nums, there is a sliding window of size\u00a0k\u00a0which is moving from the very left of the array to the very&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184,89,71],"tags":[214,217,73,213],"class_list":["post-1650","post","type-post","status-publish","format-standard","hentry","category-array","category-data-structure","category-heap","tag-deque","tag-hard","tag-heap","tag-queue","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1650","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=1650"}],"version-history":[{"count":17,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1650\/revisions"}],"predecessor-version":[{"id":3844,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1650\/revisions\/3844"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1650"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1650"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1650"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}