Przesuwne okno maksymalne

Poziom trudności Średni
Często zadawane pytania Stolica Akuna Amazonka ByteDance Cytadela Pamięci danych Dropbox Expedia Facebook Google IBM Uber
Usuń z kolejki kupa Okno przesuwneodwiedzajacy 68

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

In Przesuwne okno maksymalne problem, który daliśmy szyk nums, dla każdego sąsiedniego okna o rozmiarze k, znajdź maksymalny element w oknie.

Przykład

Wkład
nums [] = {1,3, -1, -3,5,3,6,7} k = 3
Wydajność
3,3,5,5,6,7 {}

Wyjaśnienie
Przesuwne okno maksymalneszpilka

Naiwne podejście do okna przesuwnego maksimum

Dla każdego sąsiedniego okna o rozmiarze k przejdź przez okno i znajdź maksymalny element.

  1. Uruchom pętlę od indeksu 0 do (rozmiar tablicy - k - 1)
  2. Uruchom kolejną zagnieżdżoną pętlę od indeksu i do (i + k)
  3. Zagnieżdżona pętla reprezentuje okno, znajdź maksymalną wartość wewnątrz zagnieżdżonej pętli
  4. Maksymalna wartość znaleziona powyżej jest maksymalną wartością bieżącego okna.
  5. Powtórz powyższe kroki, aby znaleźć wszystkie wartości maksymalne

Złożoność czasowa = O (n * k)
Złożoność przestrzeni = O (1)

Kod JAVA

public class Naive {
    private static int[] maxSlidingWindow(int[] nums, int k) {
        int ans[] = new int[nums.length - k + 1];
        // Traverse all the windows one by one
        for (int i = 0; i < nums.length - k + 1; i++) {
            // Initialise max as -infinite
            int max = Integer.MIN_VALUE;
            // Traverse the current window and find the maximum
            for (int j = i; j < i + k; j++) {
                max = Math.max(max, nums[j]);
            }
            // assign the current ans as maximum
            ans[i] = max;
        }
        return ans;
    }

    public static void main(String[] args) {
        // Example
        int nums[] = new int[]{1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        int max[] = maxSlidingWindow(nums, k);
        // Print the maximums
        for (int i = 0; i < max.length; i++) {
            System.out.print(max[i] + " ");
        }
    }
}
3 3 5 5 6 7

Kod C ++

#include<bits/stdc++.h> 
using namespace std;

vector<int> maxSlidingWindow(int *nums, int k, int n) {
    vector<int> ans;
    // Traverse all the windows one by one
    for (int i = 0; i < n - k + 1; i++) {
        // Initialise max as -infinite
        int max = INT_MIN;
        // Traverse the current window and find the maximum
        for (int j = i; j < i + k; j++) {
            max = std::max(max, nums[j]);
        }
        // assign the current ans as maximum
        ans.push_back(max);
    }
    return ans;
}

int main() {
    // Example
    int nums[] = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    vector<int> ans = maxSlidingWindow(nums, k, sizeof(nums) / sizeof(nums[0]));
    // Print the maximums
    for (int i = 0; i < ans.size(); i++) {
        cout<<ans[i]<<" ";
    }
    return 0;
}
3 3 5 5 6 7

Optymalne podejście do okna przesuwnego

Przechowuj pierwsze k elementów w samobalansującym BST, największy element w BST daje maksymalny element dla pierwszego okna.
W przypadku pozostałych podtablic usuń pierwszy element poprzedniego okna z samobalansującego BST i dodaj bieżący element, największy element ponownie zwraca maksymalny element w bieżącym oknie.
Aby obsłużyć przypadek powtarzających się elementów, zapisz element vs częstotliwość w BST.

Złożoność czasowa = O (n log (k))
Złożoność przestrzeni = Ok)

Kod JAVA

import java.util.TreeMap;

public class Optimal {
    private static int[] maxSlidingWindow(int[] nums, int k) {
        int ans[] = new int[nums.length - k + 1];
        TreeMap<Integer, Integer> map = new TreeMap<>();
        // Store the first k elements and their frequencies in a self balancing BST
        for (int i = 0; i < k; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i]) + 1);
            } else {
                map.put(nums[i], 1);
            }
        }
        // Largest value of BST gives the first maximum
        ans[0] = map.lastKey();
        int index = 1;
        // Traverse the remaining elements
        for (int i = k; i < nums.length; i++) {
            // Remove first element of previous window from BST
            int freq = map.get(nums[i - k]);
            if (freq == 1) {
                map.remove(nums[i - k]);
            } else {
                map.put(nums[i - k], freq - 1);
            }
            
            // Add current element to BST
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i]) + 1);
            } else {
                map.put(nums[i], 1);
            }
            
            // Current asnwer is maximum value in BST
            ans[index++] = map.lastKey();
        }
        
        return ans;
    }

    public static void main(String[] args) {
        // Example
        int nums[] = new int[]{1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        int max[] = maxSlidingWindow(nums, k);
        // Print the maximums
        for (int i = 0; i < max.length; i++) {
            System.out.print(max[i] + " ");
        }
    }
}
3 3 5 5 6 7

Kod C ++

#include<bits/stdc++.h> 
using namespace std;

vector<int> maxSlidingWindow(int *nums, int k, int n) {
    vector<int> ans;
    map<int, int> eleFreq;
    // Store the first k elements and their frequencies in a self balancing BST
    for (int i = 0; i < k; i++) {
        std::map<int, int>::iterator itr;
        itr = eleFreq.find(nums[i]);
        if (itr == eleFreq.end()) {
            eleFreq.insert(make_pair(nums[i], 1));
        } else {
            itr->second++;
        }
    }
    ans.push_back(eleFreq.rbegin()->first);
    for (int i = k; i < n; i++) {
        // Remove first element of previous window from BST
        std::map<int, int>::iterator itr = eleFreq.find(nums[i - k]);
        if (itr->second > 1) {
            itr->second--;
        } else {
            eleFreq.erase(itr->first);
        }
        
        // Add current element to BST
        itr = eleFreq.find(nums[i]);
        if (itr == eleFreq.end()) {
            eleFreq.insert(make_pair(nums[i], 1));
        } else {
            itr->second++;
        }
        
        // Current answer is maximum value in BST
        ans.push_back(eleFreq.rbegin()->first);
    }
    return ans;
}

int main() {
    // Example
    int nums[] = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    vector<int> ans = maxSlidingWindow(nums, k, sizeof(nums) / sizeof(nums[0]));
    // Print the maximums
    for (int i = 0; i < ans.size(); i++) {
        cout<<ans[i]<<" ";
    }
    return 0;
}
3 3 5 5 6 7

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »