Что подразумевается под поиском двух линий при создании контейнера?

Question

[MishaXXL]

Есть задача, дословно

Найдите две линии, которые вместе с осью x образуют контейнер, таким образом, чтобы в контейнере было больше всего воды.

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

https://leetcode.com/problems/container-with-most-...

Что подразумевается под поиском этого числа, как понять, какое нам нужно?

Comments

[res2001]

По рисунку все понятно.
В примере найдены 2 линии 2 и 9. Они образуют "двумерную" емкость в которую может поместиться 49 чего-то воды.
49 = 7*7, где
первая 7 - это расстояние между 9 и 2 линией по Х, т.е. 9-2=7
вторая 7 - это длина наименьшей из двух выбранных линий (7 и 8), т.к. именно это значение ограничивает объем получаемой емкости.

Answer 1

[Wataru]

У вас есть куча вертикальных столбиков с заданными высотами. Вам надо взять 2 столбика так, чтобы между ними было больше всего воды. Они образуют загогулину вроде |____| - это и есть контейнер, в котором может быть вода (если мир двумерный). Например если в примере взять самый левый (1) и самый правый (7) столбики, то высота воды будет 1 (иначе она слева выльется), а ширина будет 8 - итого получается 1*8=8 единиц воды.

Формально, вам надо найти такие i<j, что min(h[i],h[j])*(j-i) максимально.

Comments

[MishaXXL]

Спасибо, подскажи пожалуйста, почему в currentAreaмы ищем минимальное, а не максимальное значение?

class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;

        while (left < right) {
            int currentArea = Math.min(height[left], height[right]) * (right - left);
            maxArea = Math.max(maxArea, currentArea);

            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxArea;
    }
}

[Wataru]

MishaXXL, Потому что вам надо максимизировать min(h[i],h[j])*(j-i). Вот в currentArea вы и берете этот min из двух столбцов. А в maxArea берете максимум из значений, которые и надо максимизировать.