📟作者主頁：慢熱的陜西人

🌴專欄鏈接：力扣刷題日記

📣歡迎各位大佬👍點贊🔥關注🚓收藏，🍉留言

牛客熱題：滑動窗口的最大值

題目鏈接

滑動窗口的最大值_牛客題霸_牛客網 (nowcoder.com)

方法一：暴力

思路

• 枚舉每個區間的起始
  • 然后遍歷每個區間獲取最大值放入到ret中

代碼

vector<int> maxInWindows(vector<int>& num, int size) {int n = num.size();vector<int> ret;if(size == 0 || size > n) return ret;for(int i = 0 ; i + size - 1 < n; ++i){int max_val = -10010;for(int j = 0; j < size; ++j){max_val = max(max_val, num[i + j]);}ret.push_back(max_val);}return ret;}

復雜度

時間復雜度：O(N * M) ,其中N是數組的長度，M為size的大小

空間復雜度：O(N), 使用了一個N - size長度的數組用來返回答案

方法二：單調雙端隊列

思路

• step1：對于數組長度為0，窗口長度為0，或者窗口長度超過num的直接返回空數組
  • step2：遍歷數組，維護單調隊列，將隊列尾部小于當前數組元素的值全部出隊。
  • step3：將當前值入隊尾部
  • step4：判斷當前對頭的下標是否超過區間長度的限制，如果超過則出隊頭
  • step5：當前遍歷的數組下標大于等于區間的長度，那么則將對頭放入到答案數組
• step6：遍歷結束，返回答案數組即可

代碼

    vector<int> maxInWindows(vector<int>& num, int size) {int n = num.size();vector<int> ret; deque<int> dp;if(n == 0 || size == 0 || size > n) return ret;for(int i = 0; i < n; ++i){//除去隊列中比當前值小的值while(!dp.empty() && num[dp.back()] < num[i])dp.pop_back();//將當前下標入隊列dp.push_back(i);//判斷隊列頭部的下標是否超過序列長度if(i - dp.front() >= size)dp.pop_front();//將最大值放入到答案中if(i + 1 >= size)ret.push_back(num[dp.front()]);}return ret;}

復雜度

時間復雜度：O(N), 遍歷了一遍數組，求出了所有滑動窗口的最大值

空間復雜度：O(N)，其中開辟了N - size大小的答案數組，和最大為size長度的雙端隊列