Плъзгащ се прозорец Максимално решение LeetCode


Често задавани в Кирпич Амазонка Американ Експрес ябълка ByteDance Цитадела Google Intel LinkedIn Математика Microsoft Оракул PayPal Quora Salesforce Splunk Tesla Twilio Twitter Две сигма Uber VMware Лая
Bookin.com Категории - Трудно Автоматичен круиз Instacart tiktokПрегледи 33

Декларация за проблема

Максимално решение на плъзгащ се прозорец 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 и списък с отговори, които връщат отговора.
    • След това ще премине през масива и ще провери за условието, ако горната част на втората последователност е по-малка от текущата стойност, след което извадете елемента от опашката, в противен случай натиснете индекса на елемента в втората последователност.
    • След това отново ще проверим за две условия, ако максималният елемент не лежи в обхвата, ако няма да лежи, тогава ще го извадим от двойката и още едно условие, т.е. ако индексът е по-голям или равен на K-1, тогава ще започнете да попълвате нашия списък с отговори и добавете опашка от първия елемент в него и накрая върнете отговор.

ПРИБЛИЖАВАНЕ -

  • Първо ще създадем един Deque и един списък с отговори и накрая ще върнем отговора.
  • След това ще преминем през целия масив и с помощта на условието while ще проверим дали q[-1] < current val, ако това условие удовлетворява, тогава ще изскочи последният елемент от q. В противен случай натиснете индекса на елемента в q.
  • След това ще проверим дали максималният елемент е в обхвата или не, като използваме индекс – K == q[0]. ако условието удовлетворява, тогава ще извади елемента от q с помощта на q.popleft().
  • Отново проверете дали индексът е равен на 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 »