স্লাইডিং উইন্ডো ম্যাক্সিমাম সমস্যা
একটি অ্যারে nums এবং উইন্ডো সাইজ k দেওয়া আছে। উইন্ডো বাম থেকে ডানে এক এক করে স্লাইড করবে। প্রতিটি উইন্ডোর সর্বোচ্চ মান বের করতে হবে।
উদাহরণ: nums=[1,3,-1,-3,5,3,6,8], k=3
উইন্ডো: [1,3,-1]→3, [3,-1,-3]→3, [-1,-3,5]→5, [-3,5,3]→5, [5,3,6]→6, [3,6,8]→8
ফলাফল: [3,3,5,5,6,8]
সমাধানের পদ্ধতি (ডিক / Deque - মনোটোনিক কিউ)
- একটি ডবল-এন্ডেড কিউ
dqরাখুন যা সূচক স্টোর করবে dq-এর সামনে সবসময় বর্তমান উইন্ডোর সর্বোচ্চ মানের সূচক থাকে- নতুন উপাদান
iযোগ করার আগে:- পিছন থেকে ছোট মানवाले সূচকগুলো পপ করুন (
nums[dq.back()] < nums[i]) - সামন থেকে উইন্ডোর বাইরে যাওয়া সূচকগুলো পপ করুন (
dq.front() < i-k+1)
- পিছন থেকে ছোট মানवाले সূচকগুলো পপ করুন (
i >= k-1হলেnums[dq.front()]ফলাফলে যোগ করুন
C++ কোড উদাহরণ
ইনপুট
{1,3,-1,-3,5,3,6,8}আউটপুট
[3, 3, 5, 5, 6, 8, ]
