<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ??碼云GVP開源項目 12k star Uniapp+ElementUI 功能強大 支持多語言、二開方便! 廣告
                # 0239. 滑動窗口最大值 ## 題目地址(239. 滑動窗口最大值) <https://leetcode-cn.com/problems/sliding-window-maximum/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個數組 nums,有一個大小為 k 的滑動窗口從數組的最左側移動到數組的最右側。你只可以看到在滑動窗口內的 k 個數字。滑動窗口每次只向右移動一位。 返回滑動窗口中的最大值。 進階: 你能在線性時間復雜度內解決此題嗎? 示例: 輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 輸出: [3,3,5,5,6,7] 解釋: 滑動窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 提示: 1 <= nums.length <= 10^5 -10^4 <= nums[i] <= 10^4 1 <= k <= nums.length ``` ``` ## 前置知識 - 隊列 - 滑動窗口 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 符合直覺的想法是直接遍歷 nums, 然后然后用一個變量 slideWindow 去承載 k 個元素, 然后對 slideWindow 求最大值,這是可以的,時間復雜度是 O(n \* k).代碼如下: JavaScript: ``` <pre class="calibre18">``` <span class="hljs-keyword">var</span> maxSlidingWindow = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">nums, k</span>) </span>{ <span class="hljs-title">// bad 時間復雜度O(n * k)</span> <span class="hljs-keyword">if</span> (nums.length === <span class="hljs-params">0</span> || k === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> []; <span class="hljs-keyword">let</span> slideWindow = []; <span class="hljs-keyword">const</span> ret = []; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < nums.length - k + <span class="hljs-params">1</span>; i++) { <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> j = <span class="hljs-params">0</span>; j < k; j++) { slideWindow.push(nums[i + j]); } ret.push(<span class="hljs-params">Math</span>.max(...slideWindow)); slideWindow = []; } <span class="hljs-keyword">return</span> ret; }; ``` ``` Python3: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxSlidingWindow</span><span class="hljs-params">(self, nums: List[int], k: int)</span> -> List[int]:</span> <span class="hljs-keyword">if</span> k == <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> [] res = [] <span class="hljs-keyword">for</span> r <span class="hljs-keyword">in</span> range(k - <span class="hljs-params">1</span>, len(nums)): res.append(max(nums[r - k + <span class="hljs-params">1</span>:r + <span class="hljs-params">1</span>])) <span class="hljs-keyword">return</span> res ``` ``` 但是如果真的是這樣,這道題也不會是 hard 吧?這道題有一個 follow up,要求你用線性的時間去完成。 我們可以用雙端隊列來完成,思路是用一個雙端隊列來保存`接下來的滑動窗口可能成為最大值的數`。具體做法: - 入隊列 - 移除失效元素,失效元素有兩種 - 一種是已經超出窗口范圍了,比如我遍歷到第4個元素,k = 3,那么i = 0的元素就不應該出現在雙端隊列中了 具體就是`索引大于 i - k + 1的元素都應該被清除` - 小于當前元素都沒有利用價值了,具體就是`從后往前遍歷(雙端隊列是一個遞減隊列)雙端隊列,如果小于當前元素就出隊列` 如果你仔細觀察的話,發現雙端隊列其實是一個遞減的一個隊列。因此隊首的元素一定是最大的。用圖來表示就是: ![](https://img.kancloud.cn/a7/96/a796fa22048df6449a98d94235ba689e_623x486.jpg) ## 關鍵點解析 - 雙端隊列簡化時間復雜度 - 滑動窗口 ## 代碼 JavaScript: ``` <pre class="calibre18">``` <span class="hljs-keyword">var</span> maxSlidingWindow = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">nums, k</span>) </span>{ <span class="hljs-title">// 雙端隊列優化時間復雜度, 時間復雜度O(n)</span> <span class="hljs-keyword">const</span> deque = []; <span class="hljs-title">// 存放在接下來的滑動窗口可能成為最大值的數</span> <span class="hljs-keyword">const</span> ret = []; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < nums.length; i++) { <span class="hljs-title">// 清空失效元素</span> <span class="hljs-keyword">while</span> (deque[<span class="hljs-params">0</span>] < i - k + <span class="hljs-params">1</span>) { deque.shift(); } <span class="hljs-keyword">while</span> (nums[deque[deque.length - <span class="hljs-params">1</span>]] < nums[i]) { deque.pop(); } deque.push(i); <span class="hljs-keyword">if</span> (i >= k - <span class="hljs-params">1</span>) { ret.push(nums[deque[<span class="hljs-params">0</span>]]); } } <span class="hljs-keyword">return</span> ret; }; ``` ``` Python3: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxSlidingWindow</span><span class="hljs-params">(self, nums: List[int], k: int)</span> -> List[int]:</span> deque, res, n = [], [], len(nums) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n): <span class="hljs-keyword">while</span> deque <span class="hljs-keyword">and</span> deque[<span class="hljs-params">0</span>] < i - k + <span class="hljs-params">1</span>: deque.pop(<span class="hljs-params">0</span>) <span class="hljs-keyword">while</span> deque <span class="hljs-keyword">and</span> nums[i] > nums[deque[<span class="hljs-params">-1</span>]]: deque.pop(<span class="hljs-params">-1</span>) deque.append(i) <span class="hljs-keyword">if</span> i >= k - <span class="hljs-params">1</span>: res.append(nums[deque[<span class="hljs-params">0</span>]]) <span class="hljs-keyword">return</span> res ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:O(N)O(N)O(N) ## 擴展 ### 為什么用雙端隊列 因為刪除無效元素的時候,會清除隊首的元素(索引太小了)或者隊尾(元素太小了)的元素。 因此需要同時對隊首和隊尾進行操作,使用雙端隊列是一種合乎情理的做法。 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看