สมมติว่าเรามีอาร์เรย์ที่เรียกว่า nums มีหน้าต่างบานเลื่อนขนาด k ซึ่งเคลื่อนจากด้านซ้ายของอาร์เรย์ไปทางขวา เราจะเห็นเฉพาะตัวเลข k ในหน้าต่างเท่านั้น แต่ละครั้งที่หน้าต่างบานเลื่อนเลื่อนไปทางด้านขวาทีละตำแหน่ง เราต้องหาหน้าต่างบานเลื่อนสูงสุด ดังนั้นหากอินพุตเป็น −[1,3,-1,-3,5,3,6,8] และ k คือ 3 หน้าต่างจะเป็นแบบนี้ −
| ตำแหน่งหน้าต่าง | สูงสุด | |||||||
|---|---|---|---|---|---|---|---|---|
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | 3 |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | 3 |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | 3 |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | 5 |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | 6 |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | 8 |
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดอาร์เรย์และ
-
กำหนดหนึ่งคิวสิ้นสุดคู่ dq
-
ถ้าขนาดของ nums เท่ากับ 0 ให้คืนค่า ans
-
สำหรับการเริ่มต้น i :=0 เมื่อ i
-
ในขณะที่ dq ไม่ว่างเปล่าและ nums[องค์ประกอบสุดท้ายของ dq]
-
ลบองค์ประกอบสุดท้ายของ dq
-
-
ใส่ i ต่อท้าย dq
-
-
สำหรับการเริ่มต้น i :=k เมื่อ i
-
แทรก (nums[องค์ประกอบด้านหน้าของ dq]) ลงใน ans
-
ในขณะที่ dq ไม่ว่างเปล่าและองค์ประกอบด้านหน้าของ dq <(i-k + 1) ให้ทำ -
-
ลบองค์ประกอบด้านหน้าออกจาก dq
-
-
ในขณะที่ dq ไม่ว่างเปล่าและ nums[องค์ประกอบสุดท้ายของ dq]
-
ลบองค์ประกอบสุดท้ายของ dq
-
-
ใส่ i ต่อท้าย dq
-
-
แทรก nums[องค์ประกอบด้านหน้าของ dq] ลงใน ans ในตอนท้าย
-
กลับมาอีกครั้ง
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
void print_vector(vector<vector<auto> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector <int> ans;
deque <int> dq;
if(nums.size()==0)return ans;
for(int i =0;i<k;i++){
while(!dq.empty() && nums[dq.back()]<nums[i])dq.pop_back();
dq.push_back(i);
}
for(int i = k;i<nums.size();i++){
ans.push_back(nums[dq.front()]);
while(!dq.empty() && dq.front()<(i-k + 1))dq.pop_front();
while(!dq.empty() && nums[dq.back()]<nums[i])dq.pop_back();
dq.push_back(i);
}
ans.push_back(nums[dq.front()]);
return ans;
}
};
main(){
Solution ob;
vector<int> v = {1,3,-1,-3,5,3,6,8};
print_vector(ob.maxSlidingWindow(v,3));
} อินพุต
{1,3,-1,-3,5,3,6,8} ผลลัพธ์
[3, 3, 5, 5, 6, 8, ]
