Сначала бонусная задача: Максимум скользящего окна. Если вы уже решили ее, вам следует сначала попытаться решить проблему, которую мы сегодня обсуждаем. Если нет, то читаем описание:
Для заданного массива nums имеется скользящее окно размером k, которое перемещается с самого левого края массива на самое правое. Вы можете видеть только k чисел в окне. Каждый раз скользящее окно перемещается вправо на одну позицию. Вернуть максимальное скользящее окно.
Приведенный пример облегчает понимание.
Input: nums =[1,3,-1,-3,5,3,6,7], and k = 3 Output:[3,3,5,5,6,7] Explanation:Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
Довольно простая проблема. Попробуйте подумать над решением. Я вернусь к этой проблеме позже. Помните, решение грубой силы, которое заключается в переборе массива и для каждой позиции i, поиске максимума подмассива [i, i+k-1], запустив еще один цикл из k, выиграл не работаю здесь из-за ограничений. Временная сложность этого решения составляет O(n*k), где n — длина массива, а k — размер окна. Ограничение: 1 ≤ n ≤ 10⁵, 1 ≤ k ≤ n
Теперь давайте перейдем к реальной проблеме, которую мы здесь должны решить: Сумма подпоследовательностей с ограничениями. Вот описание:
Учитывая целочисленный массив nums и целое число k, вернуть максимальную сумму непустой подпоследовательности этого такой массив, что для каждых двух последовательных целых чисел в подпоследовательности nums[i] и nums[j], где i ‹ j выполняется условие j - i ≤ k.
Проще говоря, если вы взяли число в i-й позиции массива и хотите выбрать другое, вам нужно выбрать из следующих k элементы, находящиеся в диапазоне [i+1, i+k]. Пример:
числа = [10, -2, -10, -5, 20], к = 2
Если бы не было ограничения на k, очевидно, ответ был бы равен 30 (если взять 10 и 20 из позиций 0 и 4). Но 4-0 ≥ 2, так что это не удовлетворяет условию. Максимальная сумма в этом массиве равна 23 (10+(-2)+(-5)+20)
Теперь обсудим решение. На самом деле это довольно простая проблема DP. Нам понадобится только один параметр: pos (это индекс, в котором мы находимся). Здесь есть небольшая загвоздка: мы можем начать брать числа с любой позиции, которую захотим, но как только мы начали, мы должны поддерживать условие или игнорировать все оставшиеся элементы. Итак, мы перебираем массив, и для каждой позиции у нас есть два варианта:
- Это первый элемент, который я беру. Так что нет необходимости рассматривать предыдущие элементы.
- Это не первый элемент, поэтому должны быть некоторые элементы, которые я выбрал раньше. Поэтому постарайтесь найти максимальную сумму, которую я могу получить из предыдущих элементов.
Вот решение:
for(int i = 0; i < n; i++)
{
int mx = INT_MIN / 3;
for(int j = i-1; j >= max(0, i-k); j--)
{
mx = max(mx, dp[j]);
}
// adding mx means considering previous elements
dp[i] = max(nums[i], nums[i] + mx);
ans = max(ans, dp[i]);
}
dp[i] = max(nums[i], nums[i] + mx);
ans = max(ans, dp[i]);
}
Мы легко видим, что есть два цикла, поэтому временная сложность составляет O(n*k), что недостаточно эффективно, поскольку 1 ≤ n ≤ 10⁵, 1 ≤ k ≤ n >
Мы не можем избежать внешнего цикла. Поэтому нам нужно как-то устранить внутренний цикл. Можете ли вы узнать эту петлю и что она делает? Да, он находит максимальное значение окна размером k и каждый раз, когда окно сдвигается на одну позицию вправо. Как раз проблема, которую мы обсуждали ранее.
Существует O(n*logk)решение с помощью мультимножества. Это довольно прямолинейно и легко реализовать, и оно пройдет решение. Но мы поговорим о другом методе, который снизит сложность до O(n). Это называется Монотонная очередь.
Вот определение:
Монотонная очередь — это структура данных, в которой элементы от начала до конца строго либо увеличиваются, либо уменьшаются.
Итак, в этой задаче нам понадобится строго убывающая монотонная очередь. Как это будет работать? Приходится как-то вставлять и удалять элементы из монотонной очереди, когда окно скользит так, чтобы оно оставалось строго убывающим. В результате передний элемент всегда должен иметь максимальное значение. Этого можно достичь в два этапа:
- Мы вставим наш элемент сзади. Перед вставкой нам нужно удалить все элементы, которые меньше или равны этому элементу, чтобы он оставался строго убывающим.
- Прежде чем мы возьмем максимальное значение спереди, нам нужно убедиться, что оно принадлежит окну. Поэтому мы удалим элементы, которые не входят в этот диапазон. (Это может измениться в зависимости от проблемы)
Итак, мы видим, что у нас в основном есть два вида операций. Снятие, вставка сзади и снятие, выглядывание спереди. Deque — лучшая структура данных для реализации этого, потому что все операции, упомянутые выше, могут быть выполнены со сложностью O(1). Для лучшего понимания ниже приведен пошаговый пример:
Window position Montonic Queue Max
--------------- -------------- -----
[1 3 -1] -3 5 3 6 7 [1] -> [3] (removed 1) -> [3 -1] 3
1 [3 -1 -3] 5 3 6 7 [3 - 1 -3] 3
1 3 [-1 -3 5] 3 6 7 [-1 -3] (removed 3 from front) -> 5
[5] (removed all elements <= 5)
1 3 -1 [-3 5 3] 6 7 [5 3] 5
1 3 -1 -3 [5 3 6] 7 [6] (removed all elements <= 6) 6
1 3 -1 -3 5 [3 6 7] [7] (removed all elements <= 7) 7
Вот полное решение (здесь мы сохраняем индексы в двухсторонней очереди, но ограничение остается для элементов с этими индексами):
int ans = INT_MIN;
deque<int> dq;
for(int i = 0; i < n; i++)
{
int mx = 0;
while(!dq.empty() && dq.front() < i-k)
dq.pop_front();
dp[i] = nums[i] + (dq.empty() ? 0 : dp[dq.front()]);
while(!dq.empty() && dp[i] >= dp[dq.back()])
dq.pop_back();
if(dp[i] > 0)
dq.push_back(i);
ans = max(ans, dp[i]);
}
Вот некоторые другие проблемы, которые необходимо решить:
496. Следующий Большой Элемент I
503. Следующий Великий Элемент II
Удачного кодирования! :смайлик:
