მოცურების ფანჯარა მაქსიმალური LeetCode გადაწყვეტა

პრობლემის განცხადება

მოცურების ფანჯარა LeetCode-ის მაქსიმალური გადაწყვეტა ამბობს, რომ – თქვენ გეძლევათ მთელი რიცხვების მასივი nums, და არის მოცურების ფანჯარა ზომის k რომელიც მოძრაობს მასივის ძალიან მარცხნიდან მარჯვნივ. თქვენ შეგიძლიათ ნახოთ მხოლოდ k ნომრები ფანჯარაში. ყოველ ჯერზე, როდესაც მოცურების ფანჯარა მოძრაობს მარჯვნივ ერთი პოზიციით.

დაბრუნების მაქსიმალური მოცურების ფანჯარა.

მაგალითად 1:

შეყვანის:

 nums = [1,3,-1,-3,5,3,6,7], k = 3

გამოყვანის:

 [3,3,5,5,6,7]

განმარტება:

 
Window position                Max
---------------               -----
[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

მაგალითად 2:

შეყვანის:

 nums = [1], k = 1

გამოყვანის:

 [1]

შეზღუდვები:

• 1 <= nums.length <= 10⁵
• -10⁴ <= nums[i] <= 10⁴
• 1 <= k <= nums.length

ალგორითმი -

იდეა -

• • იმისათვის, რომ ვიპოვოთ მოცურების ფანჯრის მაქსიმუმი. პირველ რიგში, ჩვენ ყურადღებას გავამახვილებთ მოცემულ დიაპაზონზე, ანუ K და მაქსიმალური ელემენტი დევს ამ დიაპაზონში. ძირითადად რას გავაკეთებთ არის ერთი Deque and Answer სია, რომელიც აბრუნებს პასუხს.
  • შემდეგ გადაკვეთს მასივს და შეამოწმებს მდგომარეობას, თუ დეკის ზედა ნაწილი ნაკლებია მიმდინარე მნიშვნელობაზე, შემდეგ ამოიღეთ ელემენტი რიგიდან, თორემ გადაიტანეთ ელემენტის ინდექსი დეკეში.
  • შემდეგ კვლავ შევამოწმებთ ორ პირობას, თუ მაქსიმალური ელემენტი არ არის დიაპაზონში, თუ ის არ იქნება, შემდეგ ამოიღეთ იგი დეკიდან და კიდევ ერთი პირობა, ანუ, თუ ინდექსი მეტია ან ტოლია K-1-ზე, მაშინ ჩვენ დაიწყეთ ჩვენი პასუხების სიის შევსება და მასში ჩასვით პირველი ელემენტის განლაგება და ბოლოს დააბრუნეთ პასუხი.

მიდგომა -

• თავდაპირველად, ჩვენ შევქმნით ერთ Deque-ს და ერთი პასუხის ჩამონათვალს და ბოლოს დავაბრუნებთ პასუხს.
• ამის შემდეგ, ჩვენ გადავხედავთ მთელ მასივს და while პირობის დახმარებით შევამოწმებთ q[-1] < მიმდინარე val თუ ეს პირობა აკმაყოფილებს, მაშინ ამოვა ბოლო ელემენტი q-დან. წინააღმდეგ შემთხვევაში, ელემენტის ინდექსი გადაიტანეთ q-ში.
• შემდეგ ჩვენ შევამოწმებთ, არის თუ არა მაქსიმალური ელემენტი დიაპაზონში თუ არა ინდექსის გამოყენებით – K == q[0]. თუ პირობა აკმაყოფილებს, ელემენტი ამოიღებს q-დან q.popleft().
• კვლავ შეამოწმეთ, არის თუ არა ინდექსი K-1-ის ტოლი ან მეტი K-1-ზე, შემდეგ უბრალოდ დაამატეთ მაქსიმალური ელემენტი პასუხების სიაში და დააბრუნეთ პასუხი.
• აქედან გამომდინარე, ჩვენ ვიპოვით მოცურების ფანჯრის მაქსიმუმს.

გადაწყვეტის სურათი -

Pin Pin Pin Pin

 

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ans = []
        q = deque()
        
        for i,v in enumerate(nums):
            
              while(q and nums[q[-1]] <= v):
                    q.pop()
              
              q.append(i)
                
              
              if q[0] == i-k:
                    q.popleft()
              
            
              if i >= k-1:
                    ans.append(nums[q[0]])
        return ans

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) {
            return nums;
        }
        int[] ans = new int[n - k + 1];
        LinkedList<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (!q.isEmpty() && q.peek() < i - k + 1) {
                q.poll();
            }
            while (!q.isEmpty() && nums[i] >= nums[q.peekLast()]) {
                q.pollLast();
            }
            q.offer(i);
            if (i - k + 1 >= 0) {
                ans[i - k + 1] = nums[q.peek()];
            }
        }
        return ans;
    }
}

დროის სირთულე: O(N), რადგან მთელი მასივი მხოლოდ ერთხელ გავიარეთ.

სივრცის სირთულე: O(N), როგორც ჩვენ შევქმენით ერთი დეკე.

მსგავსი კითხვები - https://www.tutorialcup.com/interview/algorithm/sliding-window-technique.htm

ყველაზე მოცურების ფანჯარა-მაქსი ინტერვიუს კითხვები