Oct 26, 2020 · 3 min read
На вход даётся n чисел представляющих собой высоты столбиков, как показано на рисунке:
Представим, что мы можем заполнить всё водой. В каком контейнере воды больше?
Решение #
По сути, нужно найти площадь прямоугольника. Определимся со сторонами:
Высота наименьшего столбика одна сторона (вода не должна переливаться через край), а другая сторона — расстояние между столбиками.
Казалось бы, можно взять два самых высоких столбика, это даст максимальную высоту. Однако, они могут находиться слишком близко друг к другу. Так что выгоднее может быть взять столбики поменьше, но зато подальше друг от друга.
Лучше написать брутфорс, чем не написать ничего, поэтому так и поступим. Всегда можно перебрать все возможные варианты за квадрат и найти максимум.
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
let result = 0;
for (let i = 0; i < height.length; i++) {
for (let j = i + 1; j < height.length; j++) {
result = Math.max(result,
Math.min(height[i], height[j]) * (j - i)
);
}
}
return result;
};
Такой себе рантайм. Можно лучше?
Если интервьюер спрашивает «можно лучше» — ответ всегда да :-)
Попробуем определить где совершается лишняя работа на примере с картинки. Соберём все площади в массив, отсортируем и распечатаем.
Откуда столько повторяющихся значений? Дело в том, что площадь определяется по меньшей высоте.
В примере выше расстояние до i и j одинаковое, поэтому не имеет значение какой высоты столбики i и j если они выше. Более того, если один из них будет ниже, то мы гарантированно не получим площадь больше, площадь может только уменьшиться.
Это ключевой момент в переходе к линейному решению.
Посмотрим на перебор иначе. Будем начинать сравнение не с соседних элементов, а напротив — с краёв, т.е. фиксируем два максимально удалённых друг от друга столбика. Зачем? Чтобы одна из сторон прямоугольника гарантированно уменьшалась и не влияла на принятие решения о том куда двигаться дальше.
Далее, мы можем двигать один из двух столбиков: красный или синий, перебирая все площади. Однако, т.к. вторая сторона прямоугольника определяется по минимальной высоте, не может получиться так, что мы двигали красный столбик и получили где-то максимальную площадь.
Если встретили где-то столбики больше — это не важно, потому что минимальным всё равно остаётся синий. Если где-то меньше чем синий, тем более — площадь может только уменьшиться (помним, что второй параметр убывает и не может увеличить площадь).
Таким образом, вообще не имеет смысла сравнивать всех со всеми. На каждом шаге мы точно знаем где должен быть максимум отсекая n сравнений. Таким образом n^2 превращается просто в n.
В этом и есть суть «жадинки»: на каждой развилке ты точно понимаешь какой путь приведёт к оптимальному результату, а какой точно нет, соответственно отметаешь какое-то количество заведомо неудачных вариантов для проверки.
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
let result = 0;
+ let i = 0;
+ let j = height.length - 1;
- for (let i = 0; i < height.length; i++) {
- for (let j = i + 1; j < height.length; j++) {
+ while (i < j) {
result = Math.max(result,
Math.min(height[i], height[j]) * (j - i)
);
+ // всегда двигаем указатель на меньший столбик,
+ // т.к. заранее знаем, что, двигая указатель на больший,
+ // большей площади там не будет
+ if (height[i] < height[j]) {
+ i++;
+ } else {
+ j--;
+ }
- }
}
return result;
};
Так намного лучше! Ускорение на порядок.
PS. Обсудить можно в телеграм-чате любознательных программистов. Welcome! 🤗
Подписывайтесь на мой твитер или канал в телеграме, чтобы узнавать о новых разборах задач.