Leetcode 239.滑動視窗最大值

目錄

• 題目分析
• • 原題
  • 分析
• 完整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

分析

1、很容易想到周遊n-k+1個滑動視窗，在每一個視窗中花費線性時間k搜尋最大值，暴力解法時間複雜度為k*（n-k+1）、空間複雜度為O（1）.不滿足題目要求的線性時間。

2、由于滑動視窗每次向右移動一個機關，考慮到某種資料結構可以實作在連結清單的兩端插入和删除。故此題使用單調隊列，從左至右掃描數組，若單調隊列中所有元素均小于目前數組元素值，說明目前數組元素值必為下一滑動視窗最大值，此時将隊列中元素全部彈出後将數組元素push進隊列，否則說明目前數組元素值可能為後續某一滑動視窗最大值，将其入棧後繼續執行掃描操作，具體過程如下

滑動視窗的位置	單調隊列
[1] 3 -1 -3 5 3 6 7	-
[1 3] -1 -3 5 3 6 7	-
[1 3 -1] -3 5 3 6 7	3、-1
1 [3 -1 -3] 5 3 6 7	3、-1、-3
1 3 [-1 -3 5] 3 6 7	5
1 3 -1 [ -3 5 3 ] 6 7	5、3
1 3 -1 -3 [ 5 3 6] 7	6
1 3 -1 -3 5 [3 6 7]	7

得到的最大值數組依次取單調隊列第一個元素[3、3、5、5、6、7]

此示例沒有覆寫需要手動彈出單點隊列第一個元素的情況，若當滑動視窗向右移時，前一個視窗第一個數值恰好大于後一個視窗中所有的數值，此時需要手動彈出單調隊列中儲存的前一個數組最大值。

完整c++代碼

下面是

源代碼

。

// 單調隊列
class MonotonicQueue {
public:
   void push(int e){
       while(!data_.empty() && e > data_.back())
       data_.pop_back();//彈出小于e的元素
       data_.push_back(e);
   }
   void pop(){
       data_.pop_front();
   }
   int max() const{
       return data_.front();
   }
private:
   deque<int> data_;
};
class Solution{
public:
  vector<int> maxSlidingWindow(vector<int> & nums,int k){
      MonotonicQueue q;
      vector<int> ans;

      for(int i = 0;i < nums.size();++i){
         q.push(nums[i]);
         if(i - k + 1 >= 0) {
             ans.push_back(q.max());
             if(nums[i-k+1] == q.max()){//手動删除
                 q.pop();
             }
         }
      }
      return ans;
  }
};
           

題目總結

1、單調隊列的使用；

2、考慮手動删除不符合要求的元素。