leecode:42.接雨水

1.题目描述

2.问题分析

根据示例，雨水产生在相对低点，体积由高于低点的两边决定，然后依照短板效应取边界的较小值确定体积。
题目类型是双指针，由两边向中部移动和由中部向两侧移动均可，本例子是取最高点向两侧移动。

3.参考代码

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    var n=height.length;
    if(n <= 2) return 0;
    var max = -1, maxInd = 0;
    var i = 0;
    for(; i < n; ++i){
        if(height[i] > max){
            max = height[i];
            maxInd = i;
        }
    }
    var area = 0, root = height[0];
    for(i = 0; i < maxInd; ++i){
        if(root < height[i]) root = height[i];
        else area += (root - height[i]);
    }
    for(i = n-1, root = height[n-1]; i > maxInd; --i){
        if(root < height[i]) root = height[i];
        else area += (root - height[i]);
    }
    return area;
};

赏

感谢您的支持，加个好友吧

微信