NC128 容器盛水问题

题解

function maxWater( arr ) {
    if(arr.length <= 2){
        return 0
    }
    let res = 0
    let left = 0
    let right = arr.length - 1
    
    while(left < right){
        let minHeight = Math.min(arr[left], arr[right])
        
        while(left < right && arr[left] <= minHeight){
            res += minHeight - arr[left]
            ++left
        }
        
        while(left < right && arr[right] <= minHeight){
            res += minHeight - arr[right]
            --right
        }
    }
    return res
}

解析

if(arr.length <= 2){
    return 0
}

容器想象成一个桶，显然盛水需要至少三个元素

let minHeight = Math.min(arr[left], arr[right])

容器盛水量由最矮的边高度决定，因此获取两边最矮的高度

while(left < right && arr[left] <= minHeight)

只有比最矮的边还矮的地方可以盛水，因此可以想象将左边界向右移动，在保证新元素不会高于最矮的元素情况下（如果新元素更高，说明容器盛水量可能发生变化，要重新计算minHeight）,比minHeight还矮的位置就是可以盛水的地方。对于右边界也是一样。