Забыл упомянуть в видео, что сложность получившегося алгоритма с двумя указателями по времени у нас линейная O(n), а сложность по памяти - константа O(1).
@inzagher3 жыл бұрын
Пока не буду досматривать видео, попробую решить на литкоде) На первый взгляд просится алгоритм с квадратичной сложностью, а оказывается, можно и одним проходом справиться. Очень круто)
@MrNonameous3 жыл бұрын
А где доказательство, что такое решение будет максимальным?
@frontendscience3 жыл бұрын
@@MrNonameous В видео. Как бы странно это ни звучало) Весь алгоритм построен на принципе максимизации объема. Что я и объяснял в видео.
@ДмитрийНормов-ю6ц3 жыл бұрын
А если попадутся 2 одинаковые по высоте линии? Как тогда перемещать указатель?)))
@ШерзодТурсунов-б1ж2 жыл бұрын
@@ДмитрийНормов-ю6ц если две одинаковые по высоте линии тогда без разницы какой указатель двигать. (В видео двигается правый указатель)
@raykovskyy3 жыл бұрын
Ты уйдёшь, так и не узнав, что самый большой контейнер с водой - это моя дипломная работа...
@Александр-н1ю1п3 жыл бұрын
😂 Ай красавчик!!! Лучше и не скажешь.... Вспомнил как свою дипломную писал!!!
@valvetigu52072 жыл бұрын
Я не програмер, учился в меде. И должен вас поправить. Гомеопатия - о где главная вода!
@yurypetukhou313710 ай бұрын
Что бы я без вас дела ) Спасибо огромное
@anton-vr5xw3 жыл бұрын
Хорошая задача, и сама подача видео отличная, спасибо огромное 😌
@frontendscience3 жыл бұрын
Класс! И Вам спасибо :)
@multiply873 жыл бұрын
Просто кайфую от твоих алгоритмов)
@frontendscience3 жыл бұрын
Благодарю! Радуюсь)
@ВладимирГринько-й6с3 жыл бұрын
Нереально крутой контент🔥🔥🔥👍👍👍 Сергей, огромное спасибо за обзор и решение различных задач🤝 много полезного и интересного узнал из твоих видео👍 не сомневаюсь, что в скором времени будешь в трендах на первых местах😉 такой колоссальный труд обязательно будет оценён 💪
@frontendscience3 жыл бұрын
Ваау! Как приятно! Благодарю за поддержку и вдохновение! 🚀
@Ivan-ei5cc3 жыл бұрын
Похоже рекомендации подсказали хороший канал:)
@frontendscience3 жыл бұрын
Рады Вам! :)
@aleksberg36863 жыл бұрын
Гений!!! Все так просто решается!!! Код простой но с продуманой логикой. Благодарю за видео!!!
@frontendscience3 жыл бұрын
Благодарю Вас за поддержку! Рад, что было полезно)
@oleksandrvoron_ko5803 жыл бұрын
Як завжди круто і все чітко роз'яснено! Признаюся не рішав але код в кінці ясний, це вже хоч щось, коли розумієш рядки коду))
@frontendscience3 жыл бұрын
Да, это действительно хороший показатель. Через пару недель попробуйте вернуться к задаче, пересмотреть условие и попробовать решить по памяти. 👍
@ВладПашковский-ц2э10 ай бұрын
Большое вам спасибо
@АрсаланБазаров-л4п2 жыл бұрын
Огромное спасибо за полезный контент и доступное объяснение!!))
@theoddorrrrr3 жыл бұрын
Нереально годный контент, спасибо!
@frontendscience3 жыл бұрын
Класс! И Вам спасибо 😉
@Neravarinn3 жыл бұрын
Приветствую. Спасибо за очередную головоломку)) Недавно начал изучать js и впервые смог решить вашу задачку. К сожалению не додумался до самого оптимального способа, поэтому решил через 2 цикла. function maxArea(heights){ let area =0 let areaMax =0 if (heights.length>=2 & heights.length
@frontendscience3 жыл бұрын
Круто, что нашли решение! На собеседованиях чаще всего с этого начинают - и потом по подсказкам ищут более оптимальное решение! Успехов Вам!
@Sleep88Walker3 жыл бұрын
Хорошая подача, приятная графика
@frontendscience3 жыл бұрын
Благодарю за поддержку! Рад, что понравилось)
@ДмитрийМедыченко3 жыл бұрын
Сергей, с праздником Вас!) Спасибо большое за видео, очень интересно и доходчиво. Жду с нетерпением новых🔥👍
@frontendscience3 жыл бұрын
Вау! Точно! И Вас с праздником! 🎈🚀🎉 Спасибо большое за поддержку! Будем стараться))
@alex_osx3 жыл бұрын
отличная задачка и классное решение!
@Sk1llahh3 жыл бұрын
Привет! Все хорошо, нравится твоя подача. Но можно ли музыку потише? Либо твой голос погромче
@frontendscience3 жыл бұрын
Забыли проверить без наушников в этот раз, учтем на будущее. Благодарим.
@sokoloff1143 жыл бұрын
Спасибо за подробные объяснения, я решил через n^2 и был бы готов поспорить, что такую задачу невозможно решить через n, а вот на тебе! upd. Просмотрел все комментарии, но все решения с двумя простыми циклами немного косячные (т.е. можно подкопаться к использованию let вместо const или избыточному переприсваиванию), поэтому выкладываю свой вариант: function maxArea(heights) { let maxArea = 0; for (let i = 0; i < heights.length; i++) { for (let j = 0; j < heights.length; j++) { const area = Math.min(heights[i], heights[j]) * Math.abs(i - j); if (area > maxArea) maxArea = area; } } return maxArea; }
@frontendscience3 жыл бұрын
Отличный вариант с циклами! Благодарю за решение
@magbear32053 жыл бұрын
Больше подобного контента
@EvilYou3 жыл бұрын
Задачу решил, но решение мне самому не нравится, слишком уж громоздкое получилось. Можно сократить за счет функций, но тогда результат вместо "быстрее 85%" будет "быстрее 40%" :) Алгоритм решения: 1. В первом цикле for нахожу число, которое имеет наибольшую потенциальную площадь (если найдется идеальное второе число). 2. Во втором цикле прохожу по всем числам массива (кроме числа, которое получено в первом цикле) и нахожу то, которое в паре с первым даст максимальную площадь. 3. Может быть такой вариант, что найденная площадь хоть и близка, но не максимальна (это потому, что для расчета площади мы все равно берем наименьшее из двух и если первое число намного больше второго, никакой пользы это не принесет). Для этого начиная от первого числа до ближайшего конца массива ищу значение, которое в паре со вторым могло бы дать еще большую площадь. function maxArea(height) { let area = 0; const last = height.length - 1; let maxIndex; let maxHeight; let maxArea = 0; let secondIndex; let secondHeight; for (let i = 0; i < height.length; i++) { const current = height[i]; const maxDistance = Math.max(last - i, i); const maximalArea = maxDistance * current; if (maximalArea > maxArea) { maxArea = maximalArea; maxIndex = i; maxHeight = current; } } for (let i = 0; i < height.length; i++) { if (i === maxIndex) continue; const current = height[i]; const width = Math.abs(maxIndex - i); const currentArea = width * Math.min(maxHeight, current); if (currentArea > area) { area = currentArea; secondHeight = current; secondIndex = i; } } if (maxIndex > secondIndex) { for (let i = maxIndex + 1; i < height.length; i++) { let current = height[i]; const width = Math.abs(secondIndex - i); const currentArea = width * Math.min(secondHeight, current); if (currentArea > area) { area = currentArea; maxHeight = current; maxIndex = i; } } } else { for (let i = maxIndex - 1; i >= 0; i--) { let current = height[i]; const width = Math.abs(secondIndex - i); const currentArea = width * Math.min(secondHeight, current); if (currentArea > area) { area = currentArea; maxHeight = current; maxIndex = i; } } } return area; } Результат: Runtime: 84 ms, faster than 85.36% Memory Usage: 48.9 MB, less than 6.16% Сложность по времени: O(n) По памяти: O(1)
@frontendscience3 жыл бұрын
необычно вышло - благодарю за решение!
@wisarty2 жыл бұрын
Дякую
@maxleichenko56853 жыл бұрын
Качество видео на высоте! Сколько времени у тебя занимает подготовка одного видео?
@frontendscience3 жыл бұрын
Благодарю, приятно слышать) Очень по-разному. На это ушло 3 вечера - съемка и монтаж с отрисовкой анимации. Я ж в свободное время это делаю.
@evgeniichikishev2096 Жыл бұрын
function findMaxS(arr) { let squares = []; let count = 0; let last = arr[arr.length-1]; for (let i=arr.length-1; i>0; i--) { if (arr[i] < last) continue; if (arr[count] < last) count++; last = arr[i]; squares.push((Math.min(arr[count], last))*(i-count)); } return Math.max(...squares) }
@Proogro3 жыл бұрын
Мой вариант решение задачи. Правда, два цикла "for()". function maxArea(arr) { let max = 0, counter, numberA, numberB for(let i in arr) { counter = 0 for(let j = i; j < arr.length; j++){ const multiply = Math.min(arr[i], arr[j]) * counter if(multiply > max){ max = multiply numberA = arr[i] numberB = arr[j] } counter++ } } console.log(`${arr} Max - ${max}, numberA = ${numberA}, numberB = ${numberB}`) return max } const input = [1,8,6,2,5,4,6,3,7] console.log(`Input1 - ${maxArea(input)}`)
@frontendscience3 жыл бұрын
Благодарю за решение )
@mikhailblush52613 жыл бұрын
о, отец выспался)
@Jan_cl0d Жыл бұрын
function maxArea(heigth) { let value = 0; let left = 0; let right = heigth.length - 1; while(left < right){ if((right - left) * Math.min(heigth[left], heigth[right]) > value){ value = (right - left) * Math.min(heigth[left], heigth[right]) } (heigth[left] < heigth[right]) ? ++left : --right } return value }
@stasbelov49543 жыл бұрын
Здравствуйте. Рекурсия 10**5 раз не очень хорошо (подскажите?), но как вариант. function getMaxVolume(arr, maxVolume) { let max = maxVolume || 0 if(arr.length < 2) return max let item = arr.shift() max = Math.max(max, ...arr.map((elem, i)=>{ return Math.min(item, elem) * (i+1) })) return getMaxVolume(arr, max) } Вариант с итерацией (удалил). UPD В очередной раз понимаю, что практически нигде не говорится про алгоритмы решения задач, только вы упоминаете алгоритмы. Программировать научат на любом языке, а решать задачи, по факту, ты можешь слабо, зная только язык. Какой ресурс почитать для ознакомления со всеми алгоритмами?
@frontendscience3 жыл бұрын
Благодарю за решение. Не уверен что такой вариант пройдет на литкод, но такого решения еще не присылали ) По поводу алгоритмов: очень рекомендую книгу cracking the coding interview!
@stasbelov49543 жыл бұрын
@@frontendscience Да, на ЛитКоде решение не прошло. Как я и предполагал, слишком много памяти при больших вводных данных. Спасибо за совет книги, почитаю.
@yarik83men512 жыл бұрын
Java: public class MaxWater { public static void main(String[] args) { int[] array1 = {1, 8, 6, 2, 5, 4, 8, 3, 7}; // 49 int[] array2 = {1, 1}; // 1 int[] array3 = {4, 3, 2, 1, 4}; // 16 int[] array4 = {1, 2, 1}; // 2 System.out.println(maxArea(array1)); System.out.println(maxArea(array2)); System.out.println(maxArea(array3)); System.out.println(maxArea(array4)); } private static int maxArea(int[] arr){ int max = 0; int left = 0; int right = arr.length - 1; while(left < right) { int currentVolume = Math.min(arr[left], arr[right]) * (right - left); max = Math.max(currentVolume, max); if (arr[left] < arr[right]) { left++; } else { right--; } } return max; } }
@MultiEchelon3 жыл бұрын
Да уж, далёк я видимо от фронтенда, хотя хотел учится на эту профессию.
@serjsamoilow87113 жыл бұрын
самый большой контейнер с водой это курсы Владилена Минина
@chcylabrab3 жыл бұрын
бесплатные уроки на ютуб имеете ввиду или вы покупали и проходили платные курсы?
@serjsamoilow87113 жыл бұрын
@@chcylabrab я скачивал его платнык курсы и как по мне - водянистая вода.
@MrJohnny233 жыл бұрын
Подскажите какой ide использует автор на видео?
@frontendscience3 жыл бұрын
WebStorm
@MrJohnny233 жыл бұрын
@@frontendscience спасибо, удобные фишки есть, но блин она платная) А если из бесплатных, какую бы могли посоветовать? (По опыту)
@frontendscience3 жыл бұрын
Других не использовал, поэтому, к сожалению, не могу подсказать.
@denis_ken2 жыл бұрын
const input1 = [1, 8, 6, 2, 5, 4, 8, 3, 7]; // 49 const input2 = [1, 1]; // 1 const input3 = [4, 3, 2, 1, 4]; // 16 const input4 = [1, 2, 1]; // 2 function maxArea(height) { const max = Math.max(...height); let total = 0; for (let i = 0; i < max; i++) { let leftIdx = 0; let rightIdx = 0; let totalFromLevel = 0; for (let j = 0; j < height.length; j++) { if (height[j] >= i + 1) { leftIdx = j; break; } } for (let j = height.length - 1; j >= 0; j--) { if (height[j] >= i + 1) { rightIdx = j; break; } } totalFromLevel = (rightIdx - leftIdx) * (i + 1); if (totalFromLevel > total) total = totalFromLevel; } return total; } console.log(maxArea(input1)); console.log(maxArea(input2)); console.log(maxArea(input3)); console.log(maxArea(input4));
@vlad_issslove3 жыл бұрын
В данном видео скорее находиться площадь, а не объем. Объем - трехмерное пространосво (м3).
@frontendscience3 жыл бұрын
Да, м^3. Именно, что при постоянной глубине контейнера в 1 м переумножать на единицу все расчеты не имеет смысла. А вода измеряется объемом, но никак не площадью.
@nilsen18793 жыл бұрын
Привет, спасибо за видео. А как доказать, что с помощью 2 указателей мы найдём правильное решение? Для перебора доказательством было бы то, что по каждому проходим.
@frontendscience3 жыл бұрын
А тут мы тоже проходим по «всем большим» так как мы пытаемся максимизировать высоту линии или левой или правой и потом для найденной самой высокой,с одной из сторон, линии ищем с другой стороны линию повыше, а так как мы начинаем с противоположных сторон, мы всегда ищем с самой большой ширины.
@nilsen18793 жыл бұрын
@@frontendscience Вроде бы понял, спасибо за ответ.
@deemdeemdeem3 жыл бұрын
Кстати мне тоже это неочевидно, поэтому видео бы назвал недостаточным для решения) круто было бы наглядно показать
@frontendscience3 жыл бұрын
А как еще более наглядно Вы предлагаете это сделать? Если я уже даже анимацию нарисовал, чтоб визуализировать то, о чем рассказываю.
@CJIu3eHb3 жыл бұрын
@@deemdeemdeem Тоже сразу не понял по видео. Я бы предложил следующее объяснение. Ширина вначале у нас максимальная, берем конечные палки. Уровень определяется нижней, т.е. для низкой палки уровень не будет больше ни при какой ширине (которая может быть только меньше). Результат высчитывается и на всякий случай запоминается (вдруг это максимальный окажется). Теперь низкую палку можно откинуть, т.к. для этой ширины результат есть, другой такой ширины быть не может, она максимальная (звучит диковато, но тут и так мозги заворачиваются, так что лучше поподробнее). После откинутой палки остается текущий запомненный максимум и урезанный по ширине лес оставшихся палок. И все повторяется заново. Честно говоря, материальное представление и после этого у меня страдает, но хотя бы логически можно разрулить.
@Vel1ar13 жыл бұрын
Первое что пришло в голову, решил минут за 5. function maxArea(height) { let max = 0; return (function test() { let currentElem = height[0]; height.forEach((item, index) => { let min = Math.min(currentElem, item) if (max < min * index) { max = min * index; } }); height.splice(0, 1) if(height.length > 1) { return test(height) } return max })() }
@frontendscience3 жыл бұрын
Благодарю за решение, вышло компактно. PS: к сожалению литкод отдает Time limit exceeded на такие варианты
@Vel1ar13 жыл бұрын
@@frontendscience да, согласен, но для собеседования думаю хватит такого решения)
@sokoloff1143 жыл бұрын
@@Vel1ar1 круто, high order function, forEach, IIFE и рекурсия в одном флаконе! Интервьюер точно удивится!
@Богдан-ф8и9т3 жыл бұрын
function maxArea(arr, step) { let areas = [] for (let i = 0; i < arr.length - 1; i++) { for (let j = i + 1; j < arr.length; j++) { areas.push(Math.min(arr[i], arr[j]) * step * (j - i)) } } return Math.max(...areas) } Про дополнительные условия не вполне понял.
@frontendscience3 жыл бұрын
Благодарю за решение! Это как раз брутфорсный вариант. Дополнительные условия просто рассказывают какого размера может быть массив на leetcode и какие значения там бывают. Например из этого можно понять что делать проверку на пустой массив или то что там будет одно только число - не нужно.
@fotball27963 жыл бұрын
@@frontendscience Досмотрел до конца, не думал, что можно так изящно решить задачу за один проход.
@IsrafilGuseinov3 жыл бұрын
Привет, мог бы дать совет, как прокачать нативку, если прям туго очень? Просто решать задачки с того же литкод? Или может есть ещё какие-нибудь варианты?
@frontendscience3 жыл бұрын
Привет. Под нативкой Вы имеете в виду нативный JS? или же алгоритмы?
@IsrafilGuseinov3 жыл бұрын
@@frontendscience именно нативный, да)
@frontendscience3 жыл бұрын
@@IsrafilGuseinov ну тогда возможно какой-то курс по js пройти, чтобы систематизировать все знания и заполнить пробелы. Или например learnjavascript.ru почитать и поделать задачи.
@IsrafilGuseinov3 жыл бұрын
@@frontendscience спасибо!!
@frontendscience3 жыл бұрын
@@IsrafilGuseinov успехов!
@Tom-vr5yv3 жыл бұрын
Обьясняете хорошо но фоновая музыка местами слишком громкая
@frontendscience3 жыл бұрын
В этом видео забыли проверить громкость без наушников. Учли
Благодарю за поддержку! Решение вышло хорошее и на базовых тесткейсах отлично работает. Но вот на очень больших входящих данных на литкоде не проходит так сложность решения вышла квадратичная. Пишет: Time Limit Exceeded
@ArtemkoOnly3 жыл бұрын
Что за ide используете?
@frontendscience3 жыл бұрын
WebStorm
@oleksandr642 жыл бұрын
function area() { let max = 0; arr.forEach((item, i) => { arr.forEach((item2, i2) => { if (max < Math.min(item, item2) * (i2-i)) { max = Math.min(item, item2) * (i2-i) } }) }) return max }
@andreytarasenko19143 жыл бұрын
Мой 4-й сабмит, до этого не проходили тесткейсы( let maxArea = function (height) { let leftCurrentHeight = height[0]; let rightCurrentHeight = height[height.length - 1]; let left = 0; let right =height.length - 1; let maxS = 0; while (left rightCurrentHeight) { right -= 1; } } } return maxS; };
@frontendscience3 жыл бұрын
благодарю за решение!
@maratsultanov64623 жыл бұрын
День добрый, спасибо за интересный выпуск. А где можно найти такие же задачки, но для начинающих. Пока что сложно решать такого уровня... спасибо.
@frontendscience3 жыл бұрын
это задача Medium уровня. Можно посмотреть на задачки easy на leetcode. Или еще можно начать с задачек на codewars - выбрать 8 и 7 q там
@chcylabrab3 жыл бұрын
@@frontendscience Сергей, подскажите, medium на литкоде каким уровням равен на коудварс(хотя б примерно)? я решал только на коудварс, потому интересно сравнить с литкодом свой уровень😀
@tepliyveter89813 жыл бұрын
Подскажите название редактора кода
@frontendscience3 жыл бұрын
WebStorm
@whiteguards433 ай бұрын
идет от 1 до 8, каким образом их там 7 получается??
@Albert-jo3 жыл бұрын
Заполнял заявку, хотел бы пройти собеседование, это возможно?
@frontendscience3 жыл бұрын
Алик, если Вы заполнили заявку, она у нас точно есть. Заявок у нас очень много, поэтому существует отбор. Благодарим за доверие!
@frontendscience3 жыл бұрын
Альберт, подготовьте, пожалуйста, резюме, и заполните еще раз заявку. У нас есть лив-стрим, где можно посмотреть на подсказки, как лучше оформлять резюме (если нужно).
@maxleichenko56853 жыл бұрын
Серега, ты в фаанг готовишься ?
@frontendscience3 жыл бұрын
Ты мне все задачи перерешал на собеседовании! Приходится теперь новые искать 🥷
@SerhiyLevashov3 жыл бұрын
Если двигать только один указатель, результат не изменится. Так зачем нужен этот второй указатель?
@SerhiyLevashov3 жыл бұрын
Зря написал, надо было сначала подумать)
@Werma20063 жыл бұрын
В смысле больше 20 лет, вам сколько лет????
@frontendscience3 жыл бұрын
37 :) я начал зарабатывать фронтендом с 1-го курса университета :)
@ארטםמניאיילו3 жыл бұрын
4:00 кажется тут будет ~ О(n^2 / 2). Мы же проверяем значения по диагонали а не вообще по всему массиву
@frontendscience3 жыл бұрын
Рекомендую посмотреть видео про то, как рассчитать сложность по BIG O: kzbin.info/www/bejne/fKaXc62Hg7Njh9U
скажите, в 34 года во фронтенд разработчика уже поезд ушел или вполне реально? я НЕ гений, самый обычный ум.
@frontendscience3 жыл бұрын
Вполне реально. Выходят и позже. Успехов Вам!
@АлександрИванов-п4и9ь3 жыл бұрын
@@frontendscience ну если серьезно, работаю вообще по электронике но образование высшее техническое. Азы программирования как бы знаю и понимаю, но в 34 года мой уровень как у ребят которые в 19 лет. Кому я буду нужен старый весь когда кругом молодые все?
@frontendscience3 жыл бұрын
@@АлександрИванов-п4и9ь ну с таким подходом Вы окажитесь правым. Но я за все годы моей работы ни разу не видел, что 34 года проблема, чтоб начать. За 3 года можно вырасти до таких высот, если поставить себе цель, открыть себе любые двери! Все зависит только от человека и его мотивации. Ну и умения превратить свой прошлый опыт в плюс и ценность на новом месте и для нового работодателя.
@ded_zamay3 жыл бұрын
кто придумывает такие задачи ?
@frontendscience3 жыл бұрын
Доктор, откуда у вас такие картинки (с) 😂
@МихаилАминов-о3з Жыл бұрын
криво косо, но я пытался function maxArea(height){ let water = 0, max = 0, pointer = 0 for(let i = 0; i < height.length - 1; i++){ if(max < height[i]){ max = height[i] pointer = i } water = max > height[i + 1] ? height[i + 1] * (i - poiner + 1) : max * (i - pointer + 1) } return water }
@_imperial_67622 жыл бұрын
Для тех кто изучал С++ эта задача примитивная. Там такие задачи решают: как семечки...