Aktywne Wpisy
![MokrySuchar](https://wykop.pl/cdn/c3397992/MokrySuchar_VH07sa1QBN,q60.jpg)
MokrySuchar +108
Jest jakiś chętny reprezentant tagu #famemma wystąpić na Bitej Śmietance?
Oferujemy mysteryboxa i koszulkę (+koszty transportu).
Oferujemy mysteryboxa i koszulkę (+koszty transportu).
![Knamga](https://wykop.pl/cdn/c0834752/50e9b0ce43164ee231ff9f0f28913b17875d33628e2986b3d19e523b7ae11601,q60.jpg)
Knamga +124
Jestem prostym podlasiakiem, śmieszą mnie takie rzeczy #bialystok
![Knamga - Jestem prostym podlasiakiem, śmieszą mnie takie rzeczy #bialystok](https://wykop.pl/cdn/c3201142/5c081fd6e4d688a6de0ebb455d89e56b98e40460ab3a8d98c377bb2d76bee86d,w150.jpg)
źródło: WhatsApp Image 2024-04-24 at 17.10.51
Pobierz
Masz tablicę (powiedzmy
xs
)n
liczb i liczbęk
gdzie1 <= k <= n
. Oblicz maksymalną wartość dla kolejno każdego spójnego fragmentu tablicy o rozmiarzek
.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
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 )));
}
( ͡° ͜ʖ ͡°)
@passage: no właśnie O(k) spełnia ale czas to O(nk)
Mając taką pomocniczą strukturę, max z okienka to wartość pierwszego elementu kolejki. Jak
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).
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.