Cửa sổ trượt tối đa trong C ++

Giả sử chúng ta có một mảng gọi là nums, có một cửa sổ trượt kích thước k đang di chuyển từ bên trái của mảng sang bên phải. Chúng ta chỉ có thể nhìn thấy k số trong cửa sổ. Mỗi lần cửa sổ trượt di chuyển sang bên phải một vị trí. Chúng ta phải tìm cửa sổ trượt tối đa. Vì vậy, nếu đầu vào là - [1,3, -1, -3,5,3,6,8] và k là 3, thì cửa sổ sẽ giống như -

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định ans mảng

• Xác định một dq hàng đợi kết thúc kép

• nếu kích thước của nums bằng 0, thì trả về ans

• để khởi tạo i:=0, khi i

  • trong khi dq không trống và nums [phần tử cuối cùng của dq]

    • xóa phần tử cuối cùng của dq

  • chèn tôi vào cuối dq

• để khởi tạo i:=k, khi i

  • insert (nums [phần tử phía trước của dq]) vào ans

  • trong khi dq không trống và phần tử phía trước của dq <(i-k + 1), do -

    • xóa phần tử phía trước khỏi dq

  • trong khi dq không trống và nums [phần tử cuối cùng của dq]

    • xóa phần tử cuối cùng của dq

  • chèn tôi vào cuối dq

• chèn nums [phần tử phía trước của dq] vào ans ở cuối

• trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

{1,3,-1,-3,5,3,6,8}

Đầu ra

[3, 3, 5, 5, 6, 8, ]