Summary Ranges

Przyjrzyj się kolejno każdej wartości i zadaj sobie dwa pytania. Czy w tym miejscu zaczyna się zakres? Tak, jeśli jest to pierwsza wartość albo poprzednia wartość nie jest o jeden mniejsza. Czy w tym miejscu kończy się zakres? Tak, jeśli jest to ostatnia wartość albo następna wartość nie jest o jeden większa.

W [0, 1, 2, 5, 6, 9] zakres zaczyna się przy 0, 5 i 9, a kończy przy 2, 6 i 9. Zapamiętaj wartość, przy której zaczyna się bieżący zakres. Gdy zakres kończy się przy nums[i], zapisz "start->nums[i]" albo tylko "start", jeśli zakres zaczął się i zakończył przy tej samej wartości, tak jak w przypadku 9.

Każda wartość jest odwiedzana raz i sprawdza dwóch sąsiadów, więc czas działania wynosi O(n). Poza wynikiem przechowujesz jedną zapamiętaną wartość początkową, więc dodatkowa przestrzeń wynosi O(1).

Traktuj każdy zakres jako blok tablicy i znajdź jego oba końce. Wskaźnik i wskazuje pierwszą wartość zakresu. Wskaźnik j zaczyna od i i przesuwa się w prawo, dopóki następna wartość nie jest dokładnie o jeden większa, więc zatrzymuje się na ostatniej wartości zakresu.

Dla [-3, -1, 0, 1, 4, 7, 8]: i przy -3 nie może rozszerzyć zakresu, ponieważ -1 to nie -2, więc zakres to "-3". Następnie i przeskakuje do -1, a j przesuwa się przez 0 i 1, po czym zatrzymuje się przed 4: "-1->1". Potem "4" i "7->8". Po każdym zakresie i przesuwa się na j+1, czyli pierwszą wartość następnego zakresu.

Zakresów jest możliwie najmniej: dwie wartości oddzielone przerwą nigdy nie mogą należeć do tego samego zakresu, a ta metoda dzieli tylko w miejscach przerw. Oba wskaźniki przesuwają się wyłącznie do przodu, więc pętla wewnętrzna wykonuje się łącznie n razy we wszystkich zakresach, dzięki czemu złożoność czasowa wynosi O(n), a dodatkowe miejsce O(1).