---

Условие задачи

Дан массив. Найдите длину наименьшего подмассива, сортировка которого приведёт в порядок весь массив.

Пример 1:

Вход: [1, 2, 5, 3, 7, 10, 9, 12]
Выход: 5
Пояснение: достаточно отсортировать [5, 3, 7, 10, 9].

Пример 2:

Вход: [1, 3, 2, 0, -1, 7, 10]
Выход: 5
Пояснение: достаточно отсортировать [1, 3, 2, 0, -1].

Пример 3:

Вход: [1, 2, 3]
Выход: 0
Пояснение: массив уже отсортирован.

Пример 4:

Вход: [3, 2, 1]
Выход: 3
Пояснение: нужно отсортировать весь массив.

Решение

Сначала найдём слева и справа первые нарушения порядка. Они задают начальные границы кандидата на сортировку. Однако просто отсортировать этот участок недостаточно: его минимум может быть меньше элементов слева, а максимум — больше элементов справа.

Алгоритм:

1. Найти первую неупорядоченную пару слева и первую — справа.
2. Определить минимум и максимум внутри полученного участка.
3. Расширять левую границу, пока слева есть элементы больше минимума участка.
4. Расширять правую границу, пока справа есть элементы меньше максимума участка.

Код

package main

import "fmt"

func minimumWindowSort(arr []int) int {
	if len(arr) < 2 {
		return 0
	}

	low, high := 0, len(arr)-1
	for low < len(arr)-1 && arr[low] <= arr[low+1] {
		low++
	}
	if low == len(arr)-1 {
		return 0
	}

	for high > 0 && arr[high] >= arr[high-1] {
		high--
	}

	subarrayMin, subarrayMax := arr[low], arr[low]
	for i := low + 1; i <= high; i++ {
		if arr[i] < subarrayMin {
			subarrayMin = arr[i]
		}
		if arr[i] > subarrayMax {
			subarrayMax = arr[i]
		}
	}

	for low > 0 && arr[low-1] > subarrayMin {
		low--
	}
	for high < len(arr)-1 && arr[high+1] < subarrayMax {
		high++
	}

	return high - low + 1
}

func main() {
	fmt.Println(minimumWindowSort([]int{1, 2, 5, 3, 7, 10, 9, 12}))
	fmt.Println(minimumWindowSort([]int{1, 3, 2, 0, -1, 7, 10}))
	fmt.Println(minimumWindowSort([]int{1, 2, 3}))
	fmt.Println(minimumWindowSort([]int{3, 2, 1}))
}

Вывод:

5
5
0
3

Временная сложность

Несколько последовательных проходов по массиву занимают \(O(N)\) времени.

Пространственная сложность

Алгоритм использует постоянный объём дополнительной памяти, поэтому пространственная сложность равна \(O(1)\).

---