Equal Stacks算法实现错误排查：输出与预期结果不符

问题背景 #

三个圆柱堆叠，每个圆柱直径相同，需找出三堆叠高度相等的最大可能高度（高度为堆叠元素之和）。

示例输入 #

5 3 4
3 2 1 1 1
4 3 2
1 1 4 1

输入说明：三堆叠分别有5、3、4个圆柱，后续行对应各圆柱高度。

预期输出 #

5

你的程序输出 #

7

你的实现代码 #

function equalStacks(h1, h2, h3) {
    let sum1 = h1.reduce((acc, curr) => acc + curr)
    let sum2 = h2.reduce((acc, curr) => acc + curr)
    let sum3 = h3.reduce((acc, curr) => acc + curr)
    let minHeight = Math.min(sum1, sum2, sum3)
        
    while (!(sum1 == sum2 && sum2 == sum3)){    
        if(minHeight == 0) return 0
            
        if(sum1 > minHeight){
            sum1 -= h1.pop()
        }
        
        if(sum2 > minHeight){
            sum2 -= h2.pop()
        }
        
        if(sum3 > minHeight){
            sum3 -= h3.pop()
        }
        
        minHeight = Math.min(sum1, sum2, sum3)
        
        if(sum1 == sum2 && sum2 == sum3) return sum1
    }
}

你的实现思路 #

• 先计算三个数组的总和，确定最小高度，若最小高度为0则返回0；
• 初始化while循环，循环条件为三堆叠高度不同；
• 若堆叠高度大于当前最小高度，则弹出栈顶元素并减少对应总和；
• 更新最小高度，若三高度相等则返回该高度。

错误原因分析 #

核心错误是对堆叠元素顺序的理解偏差：
题目中每个堆叠的输入数组是从顶部到下方的顺序（第一个元素是堆叠的最顶部，最后一个是最底部），而你错误地将数组尾部元素当作顶部，使用pop()移除尾部元素，但实际上只能从顶部移除元素，对应数组的第一个元素，应该用shift()方法。

结合示例输入具体看：

1. 第一个堆叠[3,2,1,1,1]：你的代码用pop()移除尾部的1，总和从8变为7；但正确顶部是第一个元素3，移除后总和变为2+1+1+1=5。
2. 第二个堆叠[4,3,2]：你的代码用pop()移除尾部的2，总和从9变为7；正确顶部是4，移除后总和变为3+2=5。
3. 第三个堆叠[1,1,4,1]：你的代码因初始总和7等于min未操作；正确步骤是先移除顶部的1（总和变为6），再移除顶部的1（总和变为5）。

修正后三个堆叠总和均为5，与预期一致。

修正后的代码 #

function equalStacks(h1, h2, h3) {
    let sum1 = h1.reduce((acc, curr) => acc + curr)
    let sum2 = h2.reduce((acc, curr) => acc + curr)
    let sum3 = h3.reduce((acc, curr) => acc + curr)
    let minHeight = Math.min(sum1, sum2, sum3)
        
    while (!(sum1 === sum2 && sum2 === sum3)) {    
        if (minHeight === 0) return 0
            
        if (sum1 > minHeight) {
            sum1 -= h1.shift() // 改为shift()移除顶部元素（数组第一个元素）
        }
        
        if (sum2 > minHeight) {
            sum2 -= h2.shift()
        }
        
        if (sum3 > minHeight) {
            sum3 -= h3.shift()
        }
        
        minHeight = Math.min(sum1, sum2, sum3)
    }
    return sum1 // 循环结束后确保返回结果
}

内容的提问来源于stack exchange，提问作者shyshy