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


ხშირად ეკითხებიან Adobe Amazon American Express Apple ByteDance ციხედ Google Intel LinkedIn მათემატიკის სამუშაოები microsoft Oracle PayPal Quora Salesforce გაღრმავება Tesla Twilio Twitter ორი სიგმა Uber VMware Yelp
Bookin.com კატეგორიები - მძიმე საკრუიზო ავტომატიკა ინსტკარტი tiktokნახვები 6

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

მოცურების ფანჯარა 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 <= 105
  • -104 <= nums[i] <= 104
  • 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-ზე, შემდეგ უბრალოდ დაამატეთ მაქსიმალური ელემენტი პასუხების სიაში და დააბრუნეთ პასუხი.
  • აქედან გამომდინარე, ჩვენ ვიპოვით მოცურების ფანჯრის მაქსიმუმს.

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

მოცურების ფანჯარა მაქსიმალური LeetCode გადაწყვეტაPin მოცურების ფანჯარა მაქსიმალური LeetCode გადაწყვეტაPin მოცურების ფანჯარა მაქსიმალური LeetCode გადაწყვეტაPin მოცურების ფანჯარა მაქსიმალური LeetCode გადაწყვეტა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

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

Translate »