容器与大多数水算法-使用递归

Question

我正在用最多的水制作leetcode#11容器

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

给定n个非负整数a1， a2，...， an，其中每个表示坐标（i， ai）处的点。绘制n条垂直线，使得线i的两个endpoint位于（i， ai）和（i，0）。找到两条线，它们与x轴一起构成一个容器，使得容器中包含最多的水。

注意：容器不能倾斜，n至少为2。

var maxArea = function (height) {
            var list = [];
            for (var index = 1; index <= height.length; index++) {
                var eachCorr = {
                    x_corr: index,
                    y_corr: height[index - 1]
                }
                list.push(eachCorr);
            }

            var mainResult = reCursion(list, list.length-1,0,1);

            console.log(list);
            console.log(mainResult);

            return mainResult;
            //last vertical line * each vertical line from index=1; 
            //x-corr*(last vertical - each vertical), y-corr*(smaller vertical line)
        };

        function reCursion(arr, index, x,y) {
            //lastX and lastY use recursion to loop
            var lastX = arr[index][x];
            var lastY = arr[index][y];
            var chosenY = 0;
            var area = 0;
            var result = [];
            var maxAreaAns = 0;
            for (var i = index - 1; i >= 0; i--) {
                if (lastY > arr[i][1]) {
                    chosenY = arr[i][1];
                } else {
                    chosenY = lastY;
                }
                area = (lastX - arr[i][0]) * chosenY;
                console.log(`area = ${area} with i = ${i}, lastX=${lastX}, lastY=${lastY}`); 
                result.push(area);
            }
            if (index === 0) {
                maxAreaAns = Math.max(...result);
                return maxAreaAns;
            } else {
                return reCursion(arr, index - 1,0,1);
            }
        }

我的方法是使用递归，首先选择最后一条垂直线，乘以之前每条垂直线的x-corr差，然后选择比较时垂直线的小y-corr。

面积=（最后一条垂直线和比较垂直线的x-corr差值）*（小垂直线的y-coor）

然后使用递归选择倒数第二条垂直线，以此类推，直到选择第一条垂直线。

然后我将所有面积结果放入一个数组，并找到最大值。

我想知道为什么这个方法不能执行（lastX、lastY、区域变量未定义）。

Answer 1

在分析了代码之后

var lastX = arr[index][x];
var lastY = arr[index][y];

两者都始终未定义。由于arr[索引]返回的是对象而不是列表，因此无法通过索引获取值。你需要这样做

var lastX = arr[index].x_corr;
var lastY = arr[index].y_corr;

这也适用于您的

if (lastY > arr[i][1]) {
      chosenY = arr[i][1];

现在，您可能已经意识到，您的函数总是作为其结果注销Infinity。这是因为当条件

if (index === 0) {
       maxAreaAns = Math.max(...result);
       return maxAreaAns;
}

如果满足并执行其中的代码，则结果数组始终为空（请尝试在没有任何输入的情况下调用Math.max（）函数）。它将返回无穷大。

这是因为当index变量等于0时，循环

for (var i = index - 1; i >= 0; i--) {
       if (lastY > arr[i][1]) {
       ...
}

不会运行（因为i从-1开始），并且结果保持为空数组。

我猜您想要做的是将数组设置为全局变量，或者将其传递给下一个递归函数。

话虽如此，我实际上看不到使用递归解决这个问题的意义。与其使用递归（这显然使编写和理解代码变得困难），为什么不直接使用嵌套循环来检查组合呢？