Наименьший неупорядоченный подмассив

Постановка задачи

nums = [2, 6, 4, 8, 10, 9, 15]

5

nums = [1, 2, 3, 4]

0

nums = [1]

0

Решение

На первый взгляд задача кажется не очень сложной - можно просто сравнить массив с его отсортированной версией. Такое решение годится и пройдет тесты на LeetCode, но интервьюер тут же задаст вам дополнительный вопрос: "Сможете ли вы решить эту задачу за время O(n)?".

Идея решения:

Сначала подробнее рассмотрим решение через сортировку. Мы создаем копию массива, сортируем ее и сравниваем с исходным массивом, чтобы найти первые элементы слева и справа, которые стоят не на своих местах.

Вот как это может выглядеть в коде:

function findUnsortedSubarray(nums) {
    let nums2 = [...nums].sort((a, b) => a - b);
 
    let i = 0;
    while (i < nums.length && nums2[i] === nums[i]) {
        i++;
    }
 
    let j = nums.length - 1;
    while (j >= 0 && nums2[j] === nums[j]) {
        j--;
    }
 
    if (j < i) {
        return 0;
    }
    return j - i + 1;
}

Мы можем заметить, что у нас есть два указателя, один слева массива, другой справа, двигая их мы и находим границы подмассива.

Что если использовать два указателя сразу в исходном массиве, чтобы найти границы подмассива, нарушающего порядок?

Чтобы с этим разобраться, задайте себе следующие вопросы:

• Что можно сказать про ответ, если исходный массив уже отсортирован?
• А если он почти отсортирован, но есть один элемент, нарушающий порядок?

Это приводит нас к следующему наблюдению. В исходном массиве условно должны быть три отрезка, но некоторые из них могут быть пустыми:

1. Отрезок в начале массива, где все числа стоят по неубыванию.
2. Отрезок в середине массива, где порядок нарушен.
3. Отрезок в конце массива, где все числа снова стоят в порядке неубывания.

Если это так, мы могли бы пропустить первый отрезок в начале массива, затем пропустить третий отрезок от конца массива и так найти отрезок в середине.

Тут есть сложность. Если мы будем сдвигать левый указатель, пока соблюдается порядок неубывания, то найдем первый элемент, нарушающий порядок в начале массива. Аналогично при сдвиге правого указателя от конца массива мы найдем первый элемент, нарушающий порядок справа.

Проблема в том, что мы не можем просто взять эти элементы как границы. Если вы поняли почему - отлично. Если нет, вот пример: [1, 2, 5, 3, 4, 10, 11]. Здесь видно, что отрезок в начале массива 1, 2, 5 упорядочен при движении слева, а отрезок 3, 4, 10, 11 упорядочен при движении справа. То есть первый элемент слева, нарушающий порядок - это 3, а элемент справа - 5. Но 5, 3 не будет правильным ответом. Правильный ответ: 5, 3, 4. Дело в том, что максимальный элемент из отрезка в начале массива 5 больше минимального элемента 3 из отрезка в конце массива, а также больше следующего минимального элемента 4.

Так мы видим, что после нахождения отрезков 1 и 3 нужно сдвинуть их края. Край первого отрезка нужно сдвинуть влево, а край третьего отрезка - вправо. После этого оставшийся максимальный элемент в первом отрезке не должен быть больше оставшегося минимального элемента в третьем.

Это помогает нам лучше понять, что определяет границы подмассива, нарушающего порядок. Левая граница - это не просто место, где числа перестали расти. Это место, левее которого все элементы меньше минимума неупорядоченной части. Аналогично, правая граница - это место, правее которого все элементы больше максимума неупорядоченной части.

Отсюда рождается более изящная идея: вместо того чтобы сначала искать границы отрезков 1 и 3, а потом их сдвигать, мы можем сдвигать правую границу при проходе слева, а левую границу при проходе справа. Так мы найдем левую и правую границы подмассива.

Рассмотрим правую границу подмассива, нарушающего порядок. Как мы уже поняли выше, это то место, правее которого все элементы больше максимума неупорядоченной части. Мы можем найти такой элемент при движении слева от начала массива и отслеживании текущего максимума. Как только мы видим элемент, который меньше текущего максимума, правая граница точно не может быть левее этого элемента.

Аналогично, при проходе справа налево каждый элемент должен быть минимумом. Если мы видим число, которое больше текущего минимума, оно нарушает порядок и определяет левую границу подмассива.

В итоге после прохода с двух сторон мы получим две точки: последний неупорядоченный элемент справа, границу r, и последний неупорядоченный элемент слева, границу l. Расстояние между ними и будет длиной наименьшего неупорядоченного подмассива. При этом нам не нужно ничего сортировать или хранить лишние копии данных.

Основные шаги:

Вот основные шаги оптимизированного алгоритма в один проход:

1. Инициализация.

   • Устанавливаем l = -1 и r = -2. Если массив отсортирован, формула `r - l
     • 1сразу вернет0` без дополнительных условий.
   • currentMax равен первому элементу, а начальный минимум currentMin последнему.

2. Цикл: мы проходим по массиву один раз, используя индекс i для движения слева направо и вычисляемый индекс j = n - 1 - i для движения справа налево.

   • Если элемент nums[i] меньше максимума, значит, он нарушает порядок и должен быть включен в подмассив. Мы обновляем r = i. В противном случае обновляем currentMax.
   • Если элемент nums[j] больше минимума, значит, он стоит не на месте относительно правой части. Мы обновляем l = j. В противном случае обновляем currentMin.

3. Завершение цикла.

   • После завершения цикла l указывает левую границу, а r - правую. Длина подмассива вычисляется простым вычитанием: r - l + 1.

Вот как это работает на примере:

nums = `[1, 2, 5, 3, 4, 10, 11]`

1. Инициализация:
   • l = -1, r = -2
   • currentMax = 1, currentMin = 11

2. Цикл:

   2.1 i = 0, j = 6 - Слева: nums[0] = 1. Не меньше currentMax (1). Обновляем currentMax = 1. - Справа: nums[6] = 11. Не больше currentMin (11). Обновляем currentMin = 11.

2.2 i = 1, j = 5

• Слева: nums[1] = 2. Больше currentMax (1). Обновляем currentMax = 2.
• Справа: nums[5] = 10. Меньше currentMin (11). Обновляем currentMin = 10.

2.3 i = 2, j = 4

• Слева: nums[2] = 5. Больше currentMax (2). Обновляем currentMax = 5.
• Справа: nums[4] = 4. Меньше currentMin (10). Обновляем currentMin = 4.

2.4 i = 3, j = 3

• Слева: nums[3] = 3. Меньше currentMax (5). Ставим правую границу r = 3.
• Справа: nums[3] = 3. Меньше currentMin (4). Обновляем currentMin = 3.

2.5 i = 4, j = 2

• Слева: nums[4] = 4. Меньше currentMax (5). Ставим правую границу r = 4.
• Справа: nums[2] = 5. Больше currentMin (3). Ставим левую границу l = 2.

2.6 i = 5, j = 1

• Слева: nums[5] = 10. Больше currentMax (5). Обновляем currentMax = 10.
• Справа: nums[1] = 2. Меньше currentMin (3). Обновляем currentMin = 2.

2.7 i = 6, j = 0

• Слева: nums[6] = 11. Больше currentMax (10). Обновляем currentMax = 11.
• Справа: nums[0] = 1. Меньше currentMin (2). Обновляем currentMin = 1.

3. Завершение цикла.
   • Получили границы: l = 2 и r = 4
   • Вычисляем длину: 4 - 2 + 1 = 3

Итог: 3 (подмассив [5, 3, 4]).

Оценка сложности

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

Временная сложность равна O(n), так как мы делаем один проход по массиву.

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

Мы не создаем никаких дополнительных структур данных, кроме переменных для указателей, поэтому пространственная сложность равна O(1).

Код решения

Приведем код решения.

func findUnsortedSubarray(nums []int) int {
    n := len(nums)
    l := -1
    r := -2
    currentMax := nums[0]
    currentMin := nums[n - 1]
    for i := 0; i < n; i++ {
        if nums[i] < currentMax {
            r = i
        } else {
            currentMax = nums[i]
        }
 
        j := n - 1 - i
        if nums[j] > currentMin {
            l = j
        } else {
            currentMin = nums[j]
        }
    }
    return r - l + 1
}

Итоги

Вот основные итоги по задаче, которые раскрывают ее внутреннюю логику и важные детали:

1. Поиск границ подмассива. Границы определяются глобальными экстремумами: правая граница сдвигается, когда число меньше накопленного максимума слева, а левая - когда число больше накопленного минимума справа.

2. Инициализация границ значениями l = -1 и r = -2. Она позволяет избежать дополнительных проверок в конце. Если массив изначально отсортирован, переменные не обновятся, и формула r - l + 1 автоматически выдаст 0.

3. Симметрия двух указателей. Использование двух встречных указателей внутри одного цикла позволяет одновременно искать обе границы. При проходе слева мы фиксируем правую границу, а при проходе справа - левую.

4. Граничный случай. Алгоритм устойчив к повторяющимся числам, например [1, 2, 2, 2]. Благодаря строгим знакам сравнения (< и >), дубликаты не считаются нарушением порядка и не расширяют границы подмассива.