[NotABigFan]

Kolejne zadanko na miło spędzone popołudnie. Tak jak poprzednie: nieco trikowe i również jak poprzednie zadawane m.in. przez Google na kochanych przez wszystkich whiteboardowych sesjach rekrutacyjnych.

Masz tablicę (powiedzmy xs) n liczb i liczbę k gdzie 1 <= k <= n. Oblicz maksymalną wartość dla kolejno każdego spójnego fragmentu tablicy o rozmiarze k.

np. xs=[10, 5, 2, 7, 8, 7] i k=3 -> [10, 7, 8, 8], ponieważ:

10 = max(10, 5, 2)
7 = max(5, 2, 7)
8 = max(2, 7, 8)
8 = max(7, 8, 7)

Czas O(n) i pamięć O(k). Można modyfikować tablicę i nie trzeba pamiętać całego wyniku, wystarczy wypisywanie tych liczb pojedynczo.

#programowanie #dailycodingproblem

[passage]

@NotABigFan:
const xs = [10, 5, 2, 7, 8, 7];
const k = 3;

for(let i = 0; i < xs.length - k + 1; i++) {
console.log(Math.max(...xs.slice(i, i + k )));
}
( ͡° ͜ʖ ͡°)

[NotABigFan]

@passage: oddzwonimy ( ͡° ͜ʖ ͡°)

[baalder363]

@NotABigFan: Mam noobskie pytanie: czym jest kolejny spójny fragment tablicy?

[passage]

@NotABigFan: nie wiem jak z O(k) ale O(n) spełnia ( ͡° ͜ʖ ͡°)

[NotABigFan]

@baalder363: kolejne czyli np xs[0:k], xs[1:k+1], ...
@passage: no właśnie O(k) spełnia ale czas to O(nk)

[D.....n]

@NotABigFan: Utrzymywać pomocniczą "kolejkę" elementów z obserwowanego okienka w taki sposób, że elementy w tej kolejce są w porządku nierosnącym. Tzn. elementem kolejki jest para (indeks, wartość), kolejne elementy są w stronę rosnących indeksów i malejących wartości. Taka kolejka ma maksymalnie k elementów. Może mieć mniej, jeśli obserwowane okienko nie jest złożone z elementów nierosnących, tylko ma ekstrema.

Mając taką pomocniczą strukturę, max z okienka to wartość pierwszego elementu kolejki. Jak

[NotABigFan]

@Demolicjon: Sorry albo nie do końca rozumiem albo to nie amortyzuje się do O(n). Czym się ta Twoja kolejka różni od kopca? Jak chcesz utrzymać niezmiennik kiedy maksymalny element zostanie usunięty z kolejki?

[D.....n]

@NotABigFan: Zwizualizuj sobie tę kolejkę jako np. listę wskaźnikową. Max jest z lewej strony. Jak wywalisz maksymalny element, to drugi masz zaraz obok i nie musisz już niczego przestawiać (dzięki niezmiennikowi). O(1) operacja.

Jak pojawia się nowy element, to dla zachowania niezmiennika być może musisz coś wywalić z prawej strony. Wywalenie jednego elementu kosztuje O(1), potem wstawienie O(1). Łącznie masz max. n wstawień i usunięć, więc amortyzuje się do O(n).

[NotABigFan]

@Demolicjon: Chyba jarze, jeszcze to sobie zakodze dla pewności bo moje rozwiązanie było bardziej skomplikowane

[D.....n]

@NotABigFan: A jakie było Twoje?

[NotABigFan]

@Demolicjon: Zakodziłem tę kolejkę przy użyciu deque i wygląda na to, że działa: https://pastebin.com/Cz4GhABb

[NotABigFan]

@Demolicjon: Moje to było coś takiego: https://pastebin.com/U5xwqYKS
Wczytywałem k elementów, liczyłem dla nich max-sufiksy, tak, że wiedziałem jaki będzie kolejny maks po usunięciu tego z lewej. Jednocześnie doczytując z prawej jeden element i porównując go z największym. Jeżeli doczytałem k elementów to znów liczyłem te maks sufiksy.

[D.....n]

@NotABigFan: No to właściwie jest dokładnie ten sam algorytm.