如何使用C++求滑動窗口最大值

這篇文章主要為大家展示了“如何使用C++求滑動窗口最大值”，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“如何使用C++求滑動窗口最大值”這篇文章吧。

一、題目描述

給你一個整數數組 nums，有一個大小為 k 的滑動窗口從數組的最左側移動到數組的最右側。你只可以看到在滑動窗口內的 k 個數字?；瑒哟翱诿看沃幌蛴乙苿右晃?。

返回滑動窗口中的最大值。

示例 1：
輸入：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

示例 2：
輸入：nums = [1], k = 1
輸出：[1]

示例 3：
輸入：nums = [1,-1], k = 1
輸出：[1,-1]

提示：1 <= nums.length <= 10e5-10e4 <= nums[i] <= 10e41 <= k <= nums.length

二、題解

(1) 暴力遍歷法

這種方法思路比較簡單、直接：從左向右依次滑動窗口的過程中，計算每一次的最大值，存入ans中。

class Solution {
   
   
   public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {
   
   
   vector<int> ans;int max;for(int i=0; i<nums.size()-k+1; ++i){
   
   
   max = nums[i];for(int j=i; j<i+k; ++j){
   
   
   if(nums[j]>max)max = nums[j];}ans.push_back(max);}return ans;}};

這種方法時間復雜度O(nk)，會超出時間限制，因此需要進行一些優化！

(2) 優先隊列

對于本題，兩個相鄰（只差了一個位置）的滑動窗口，它們共用著 k-1 個元素，而只有 1個元素是變化的，我們可以根據這個特點進行優化。

優先隊列priority_queue與普通隊列queue的不同之處在于，它包含的最大值元素位于隊首，因此這是一種非常合適解決此類問題的數據結構。

C++中，優先隊列priority_queue類的具體用法可參見：【C++養成計劃】隊列 —— 快速上手STL queue類（Day13）

對于本題而言，具體步驟是：

• 將數組 nums 的前 k 個元素放入優先隊列中，并找出第一個窗口的最大值，存入ans中

• 向右移動窗口時，把一個新的元素放入優先隊列中，此時堆頂的元素就是堆中所有元素的最大值。

• 根據最大元素的索引號判斷：該元素是否屬于該窗口內，從而刪除不屬于當前窗口的所有較大值。直到最大值屬于當前的窗口，該值極為當前窗口的最大值。

class Solution {
   
   
   public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {
   
   
   int n = nums.size();priority_queue<pair<int, int>> q;// 將數組 nums 的前 k 個元素放入優先隊列中for (int i = 0; i < k; ++i) {
   
   
   q.emplace(nums[i], i);}vector<int> ans = {
   
   
   q.top().first};for (int i = k; i < n; ++i) {
   
   
   // 把一個新的元素放入優先隊列中q.emplace(nums[i], i);while (q.top().second <= i - k) {
   
   
   // 如果優先隊列的最大值不屬于當前窗口，則刪掉該最大值q.pop();}// 剩下的里面最大值即可ans.push_back(q.top().first);}return ans;}};

復雜度分析：

• 時間復雜度：O(nlogn)，其中 n 是數組 nums 的長度。由于將一個元素放入優先隊列的時間復雜度為 O(logn)，因此總時間復雜度為 O(nlogn)。

• 空間復雜度：O(n)，即為優先隊列需要使用的空間。

注：這里所有的空間復雜度分析都不考慮返回的答案需要的 O(n) 空間，只計算額外的空間使用。

以上是“如何使用C++求滑動窗口最大值”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！