Выбор ответа Middle Два указателя обновлено
Контейнер с водой
Вопрос
Задача «самый большой контейнер с водой» (максимум min(h[l], h[r]) * (r - l)). Почему двигают указатель на меньшей высоте?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Сдвиг большей стороны не может увеличить площадь контейнера. Площадь ограничена меньшей стенкой.
Варианты ответа
- Так цикл заканчивается быстрее, чем при сдвиге большей
- Меньшая высота всегда стоит ближе к концу массива
- Сдвиг большей стороны не может увеличить площадь контейнераправильный ответ
- Двигать можно любую сторону, ответ получится тот же
Разбор
Площадь ограничена меньшей стенкой. Если сдвинуть большую, ширина уменьшится, а min-высота не вырастет: такой вариант заведомо не лучше. Значит, меньшую стенку можно отбросить. Это доказывает корректность O(n) решения.
- Цикл заканчивается за n шагов при любом выборе, дело не в скорости.
- Положение меньшей высоты ничем не определено.
- Если двигать большую, можно пропустить оптимум.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.