如何使用C++求滑動(dòng)窗口最大值

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

一、題目描述

給你一個(gè)整數(shù)數(shù)組 nums，有一個(gè)大小為 k 的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)。你只可以看到在滑動(dòng)窗口內(nèi)的 k 個(gè)數(shù)字?；瑒?dòng)窗口每次只向右移動(dòng)一位。

返回滑動(dòng)窗口中的最大值。

示例 1：
輸入：nums = [1,3,-1,-3,5,3,6,7], k = 3
輸出：[3,3,5,5,6,7]
解釋：
滑動(dòng)窗口的位置                 最大值
---------------               -----
[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) 暴力遍歷法

這種方法思路比較簡(jiǎn)單、直接：從左向右依次滑動(dòng)窗口的過程中，計(jì)算每一次的最大值，存入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;}};

這種方法時(shí)間復(fù)雜度O(nk)，會(huì)超出時(shí)間限制，因此需要進(jìn)行一些優(yōu)化！

(2) 優(yōu)先隊(duì)列

對(duì)于本題，兩個(gè)相鄰（只差了一個(gè)位置）的滑動(dòng)窗口，它們共用著 k-1 個(gè)元素，而只有 1個(gè)元素是變化的，我們可以根據(jù)這個(gè)特點(diǎn)進(jìn)行優(yōu)化。

優(yōu)先隊(duì)列priority_queue與普通隊(duì)列queue的不同之處在于，它包含的最大值元素位于隊(duì)首，因此這是一種非常合適解決此類問題的數(shù)據(jù)結(jié)構(gòu)。

C++中，優(yōu)先隊(duì)列priority_queue類的具體用法可參見：【C++養(yǎng)成計(jì)劃】隊(duì)列 —— 快速上手STL queue類（Day13）

對(duì)于本題而言，具體步驟是：

• 將數(shù)組 nums 的前 k 個(gè)元素放入優(yōu)先隊(duì)列中，并找出第一個(gè)窗口的最大值，存入ans中

• 向右移動(dòng)窗口時(shí)，把一個(gè)新的元素放入優(yōu)先隊(duì)列中，此時(shí)堆頂?shù)脑鼐褪嵌阎兴性氐淖畲笾怠?/p>

• 根據(jù)最大元素的索引號(hào)判斷：該元素是否屬于該窗口內(nèi)，從而刪除不屬于當(dāng)前窗口的所有較大值。直到最大值屬于當(dāng)前的窗口，該值極為當(dāng)前窗口的最大值。

class Solution {
   
   
   public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {
   
   
   int n = nums.size();priority_queue<pair<int, int>> q;// 將數(shù)組 nums 的前 k 個(gè)元素放入優(yōu)先隊(duì)列中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) {
   
   
   // 把一個(gè)新的元素放入優(yōu)先隊(duì)列中q.emplace(nums[i], i);while (q.top().second <= i - k) {
   
   
   // 如果優(yōu)先隊(duì)列的最大值不屬于當(dāng)前窗口，則刪掉該最大值q.pop();}// 剩下的里面最大值即可ans.push_back(q.top().first);}return ans;}};

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：O(nlogn)，其中 n 是數(shù)組 nums 的長(zhǎng)度。由于將一個(gè)元素放入優(yōu)先隊(duì)列的時(shí)間復(fù)雜度為 O(logn)，因此總時(shí)間復(fù)雜度為 O(nlogn)。

• 空間復(fù)雜度：O(n)，即為優(yōu)先隊(duì)列需要使用的空間。

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

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