Постановка задачи
В очереди стоят N детей, и каждому ребенку присваивается рейтинг. Вы даете этим детям конфеты, следя за тем, чтобы каждый ребенок имел хотя бы одну конфету, а дети с более высоким рейтингом получали больше конфет, чем их соседи. Какой минимум конфет вы должны дать?
Примеры:
- Ввод: [1, 0, 2] | Выход: 5 {Распространение: [2, 1, 2]}
- Ввод: [1, 2, 2] | Результат: 4 {Распространение: [2, 1, 1]}
- Ввод: [0, 2, 0, 6, 6] | Выход: 7 {Распространение: [1, 2, 1, 2, 1]}
Решение 🍬— Сложность времени и пространства O (n)
По сути, каждый ребенок должен оценить обоих соседей (предыдущего ребенка и следующего ребенка), чтобы найти количество конфет, которое он должен получить:
- Если у ребенка больше, чем у соседа, то ребенок должен получить больше конфет, чем у соседа.
- Если ребенок имеет рейтинг ниже или равен рейтингу соседа (ей), то соседей можно игнорировать, поскольку это не влияет на количество конфет данного ребенка.
Конкретные шаги алгоритма и его кода следующие:
- Вперед: начните обход рейтингов с первого ребенка и обновите счетчик конфет следующего ребенка по пути. Если рейтинг текущего ребенка меньше, чем рейтинг следующего ребенка, то количество конфет следующего ребенка должно быть как минимум на на 1 больше, чем количество конфет текущего ребенка.
- Обратный обход: начните обход рейтингов с последнего ребенка и обновите счетчик конфет предыдущего ребенка по пути. Если рейтинг текущего ребенка меньше, чем рейтинг предыдущего ребенка, то количество конфет предыдущего ребенка должно быть как минимум на на 1 больше, чем количество конфет текущего ребенка.
- Подсчитайте конфеты: подсчитайте сумму подсчетов конфет для каждого ребенка для окончательного подсчета.
// Language: Java
// Time Complexity: O(n) 3 Linear traversals.
// Space Complexity: O(n) Array of candies.
public int candy(int[] ratings) {
if (ratings.length < 2) {
return ratings.length;
}
int[] candies = new int[ratings.length];
Arrays.fill(candies, 1);
// ** Step 1: Forward **
for (int i=0; i<ratings.length-1; i++) {
if (ratings[i] >= ratings[i+1]) {
continue;
}
candies[i+1] = candies[i] + 1;
}
// ** Step 2: Backward **
for (int i=ratings.length-1; i>0; i--) {
if (ratings[i] >= ratings[i-1]) {
continue;
}
candies[i-1] = Math.max(candies[i] + 1, candies[i-1]);
}
// ** Step 3: Count Candies **
int count = 0;
for (int i=0; i<candies.length; i++) {
count += candies[i];
}
return count;
}
Это вполне приемлемое решение, но мы можем сэкономить место, оптимизировав алгоритм в следующем разделе.
🍬 Оптимизация пространства - O (n) - ›O (1)
Введение в основы
Представим себе распределение входных данных [0, 4, 9, 25, 8, 6, 5] следующим образом:
Вот несколько важных наблюдений:
- 📈 Наклон вверх (возрастающие числа) для [0, 4, 9, 25]
length = 4. - Количество конфет в восходящем наклоне составляет 10 = 1 + 2 + 3 + 4, что является суммой последовательно увеличивающихся чисел с n = length = 4 (n * n + 1/2).
- 📉 Наклон вниз (убывающие числа) для [25, 8, 6, 5] имеет длину = 4.
- Количество конфет на нисходящем наклоне составляет 10 = 4 + 3 + 2 + 1, что является суммой последовательно увеличивающихся чисел с n = length = 4 (n * n + 1/2).
- Пик для обоих склонов - средний ребенок с рейтингом 25.
Количество конфет для пика
Равные уклоны
Счетчик конфет для рейтинга 25 (пик) равен 4. Это длина самого длинного склона, на котором он является пиком. В этом примере оба склона с левой и правой стороны совпадают длиной 4.
Это имеет смысл, поскольку более длинный наклон означает больше ударов по 1, чтобы ребенок получил больше конфет, чем его сосед. В конце концов, ребенок на пике склона получит максимальное количество конфет.
Давайте поднимемся по нисходящему склону [0, 4, 9, 25, 8, 6, 5] и выполним несколько конфетных заданий:
- Рейтинг 5: 1 конфета; это минимальная сумма.
- Рейтинг 6: 2 конфеты ›рейтинг 5.
- Рейтинг 8: 3 конфеты ›рейтинг 6.
- Рейтинг 25: 4 конфеты ›рейтинг 8.
Однако проблема заключается в общем количестве конфет и не требует от нас поиска назначения конфет / детей, как описано выше.
Помня об этом, давайте спустимся по тому же спуску в [0, 4, 9, 25, 8, 6, 5] и выполним несколько конфетных заданий:
- Рейтинг 25: 4 конфеты ›рейтинг 9.
- Рейтинг 8: 1 конфета; это минимальная сумма.
Это никак не повлияет на количество конфет на пике, так как в нем должно быть не менее 1 + 1 = 2 леденца, а у него уже есть 4. - Рейтинг 6: 2 конфеты; нисходящий склон (без пика) имеет 2 детей [8,6]. В идеале с рейтингом 6 должна быть 1 конфета, а с рейтингом 8 - 2 конфеты, чтобы соблюсти ограничение: более высокий рейтинг = больше конфет. Поскольку нас не волнует точная пара «ребенок-леденец», такая замена безвредна.
Это не влияет на количество леденцов на пике, так как в нем должно быть не менее 2 + 1 = 3 конфеты, а в нем уже 4 . - Рейтинг 5: 3 конфеты; нисходящий наклон имеет 3 детей [8, 6, 5].
В идеале рейтинг 5 должен иметь 1 конфету, рейтинг 6 должен иметь 2 конфеты, а рейтинг 8 должен иметь 3 конфеты, чтобы сохранить ограничение более высокого рейтинга = больше конфет. Поскольку нас не волнует точная пара «ребенок-леденец», такая замена безвредна.
Это не влияет на количество леденцов на пике, так как в нем должно быть не менее 3 + 1 = 4 леденца, а у него уже есть 4 .
Преимущество описанного выше подхода заключается в том, что длина нисходящего наклона просто определяет количество конфет, которое нужно дать ребенку.
Неравномерные уклоны
Добавим в конец ребенка с рейтингом 4.
В дополнение к шагам, описанным в предыдущем разделе, присвойте 4 леденцам рейтинг 4, потому что нисходящий наклон теперь имеет 4 дочерних элемента [8, 6, 5, 4].
Влияет ли это на пик с рейтингом 25? В нем 4 конфеты. Учитывая наклон длиной 4 перед ним, у него должно быть 5 конфет для поддержания ограничения более высокого рейтинга = больше конфет.
Так как же это исправить?
Мы находим разницу наклона: если размер этого нисходящего наклона больше или равен восходящему наклону (4 ≥ 4), тогда прибавляем 1 (разница наклона) к количеству конфет. С выпуклостью 1, 4 фактически превратится в 5 на пике.
Давайте добавим еще одного ребенка с рейтингом 3 в конце.
В дополнение к шагам, описанным выше, присвойте 5 леденцам рейтинг 3, потому что у нисходящего склона теперь 5 детей [8, 6, 5, 4, 3].
Поскольку размер нисходящего наклона больше, чем восходящего (5≥4), добавьте 1 к общему количеству конфет. С ударом 1, 5 фактически превратится в 6 на пике.
Код алгоритма следующий:
// Language: Java
// Time Complexity: O(n) Linear traversal.
// Space Complexity: O(1) Constant space for variables.
public int candy(int[] ratings) {
if (ratings.length < 2) {
return ratings.length;
}
int count = 1;
int upSlopeLength = 0;
int upSlope = 0;
int downSlope = 0;
for (int i=1; i<ratings.length; i++) {
int previous = ratings[i-1];
int me = ratings[i];
// ** Equal Ratings **
if (me == previous) {
upSlope = 0;
downSlope = 0;
upSlopeLength = 0;
count += 1;
// ** Upward Slope **
} else if (me > previous) {
upSlope = upSlope == 0 ? 1 : upSlope;
upSlope += 1;
downSlope = 0;
count += upSlope;
upSlopeLength = upSlope;
// ** Downward Slope **
} else {
upSlope = 0;
downSlope += 1;
int slopeDiff =
(downSlope + 1 - upSlopeLength) > 0 ? 1 : 0;
count += downSlope + slopeDiff;
}
}
return count;
}
Если вы нашли эту статью полезной, пожалуйста, помогите мне привлечь больше учеников-разработчиков!
Покажите, дав «хлопки» 👏 на левом поле страницы (на рабочем столе) или внизу (на мобильном устройстве). Вы можете сделать это до 50 раз, нажимая постоянно!
Анум Малик
Следите за новостями NMTechBytes в Twitter, где я каждый день пишу о технических новинках :)
