Жылдыруучу терезенин максималдуу LeetCode чечими


Көп суралган Adobe Amazon American Express алма ByteDance Citadel Гугл Intel LinkedIn Математика иштери Microsoft Oracle PayPal Quora Сатуу бөлүмү Splunk Tesla Twilio Twitter эки Sigma Uber VMware Yelp
Bookin.com Категориялар - Hard Круиздик автомат Instacart дни SeishViews 33

Маселени билдирүү

Жылдыруучу терезенин максималдуу LeetCode чечими мындай дейт: - Сизге бүтүн сандардын массивдери берилет nums, жана көлөмү жылма терезе бар k ал массивдин эң сол жагынан эң оң жагына жылып жатат. Сиз гана көрө аласыз k терезеде сандар. Ар бир жолу жылма терезе оңго бир позицияга жылат.

Return максималдуу жылма терезе.

Мисал 1:

киргизүү:

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

Output:

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

Explanation:

 
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

Output:

 [1]

Чектөөлөр:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length

АЛГОРИТМ –

ИДЕЯ –

    • Жылдыруучу терезенин максималдуу өлчөмүн табуу үчүн. Биринчиден, биз берилген диапазонго көңүл бурабыз, башкача айтканда, K жана максималдуу элемент ошол диапазондо. Негизинен биз кыла турган нерсе - жоопту кайтарган бир Deque жана Answer тизмесин түзүү.
    • Андан кийин массивди аралайт жана шартты текшериңиз, эгерде декенин үстү учурдагы мааниден аз болсо, андан кийин элементти кезектен чыгарып салыңыз, болбосо элементтин индексин декеге түртүңүз.
    • Андан кийин биз дагы эки шартты текшеребиз, эгерде максималдуу элемент диапазондо жатпаса, анда ал жатпаса, анда аны деквден чыгарып салабыз жана дагы бир шарт, башкача айтканда, индекс K-1ден чоң же барабар болсо, анда биз жооп тизмегибизди толтуруп баштаңыз жана ага биринчи элементтин кезексиздигин кошуп, акырында жооп кайтарыңыз.

МАМИЛЕ -

  • Адегенде биз бир Deque жана бир жооп тизмесин түзөбүз жана акырында жоопту кайтарабыз.
  • Андан кийин, биз бүт массивди кыдырып чыгабыз жана while шартынын жардамы менен q[-1] < учурдагы val болсо, эгерде бул шарт канааттандырылса, анда qдан акыркы элементти чыгарабыз. Болбосо элементтин индексин qга түртүңүз.
  • Андан кийин биз индекс – K == q[0] аркылуу максималдуу элемент диапазондо жатабы же жокпу текшеребиз. эгерде шарт канааттандырылса, анда q.popleft() аркылуу q элементин чыгарат.
  • Индекс K-1ге барабарбы же K-1ден чоңбу, кайра текшериңиз, андан кийин жооп тизмесине максималдуу элементти кошуп, жоопту кайтарыңыз.
  • Демек, биз жылма терезенин максималдуу өлчөмүн табабыз.

ЧЕЧИМДИН СҮРӨТҮ –

Жылдыруучу терезенин максималдуу LeetCode чечимитөөнөч Жылдыруучу терезенин максималдуу LeetCode чечимитөөнөч Жылдыруучу терезенин максималдуу LeetCode чечимитөөнөч Жылдыруучу терезенин максималдуу LeetCode чечимитөөнөч

 

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), биз бир Deque жараткан сыяктуу.

ОКШОШ СУРООЛОР - https://www.tutorialcup.com/interview/algorithm/sliding-window-technique.htm

Жогорку жылдыргыч терезе-макси интервью суроолору

Translate »