LeetCode 42. 接雨水

发表于 | 分类于 | 评论数： | 阅读次数：

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例:

1
2
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

题解:
  每个位置上能存多少水取决于它左右两侧的最高峰较低的那一峰的高度，比如图中第六个位置上，它左侧最高为2格，右侧最高为3格，所以这一列的水位能到2格的高度。
  所以我们的算法就是：首先从左往右扫一趟数组，算出每个位置上左侧的最高峰；再从右往左扫一趟数组，算出每个位置上右侧的最高峰。最后遍历一遍求出每个位置上的积水量。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))

int trap(int *height, int heightSize)
{
    if(!heightSize)
        return 0;
    int ans = 0, temp, i;
    int leftTop[heightSize], rightTop[heightSize];

    /* 计算leftTop和rightTop */
    for(i = 1, leftTop[0] = 0; i < heightSize; ++i)
        leftTop[i] = max(leftTop[i-1], height[i-1]);
    for(i = heightSize-2, rightTop[heightSize-1] = 0; i >= 0; --i)
        rightTop[i] = max(rightTop[i+1], height[i+1]);

    for(i = 0; i < heightSize; ++i)
    {
        temp = min(leftTop[i], rightTop[i]) - height[i];
        if(temp > 0)
            ans += temp;
    }
    return ans;
}

  这种解法遍历了三趟数组，所以时间复杂度为 O(n)。用到了 leftTop 和 rightTop 两个数组，所以空间复杂度也是 O(n)。

  官方题解提供了一种更优秀的解法，可以只遍历一次数组，且空间复杂度为 O(1)：
  双指针法，一个指针从左往右移动，另一个从右往左移动。维护两个变量 left_max 和 right_max ，分别存储左右两边目前为止遇到的最高峰。
  一开始，两个指针分别指向最左侧和最右侧的元素。如果左侧指针的高度比右侧矮，左侧指针就右移一格，否则就右侧指针左移。换句话说，就是始终保持对侧是不矮于本侧的。这样一来，水能存多高就只取决于本侧的最大高度了。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int trap(vector<int>& height)
{
    int left = 0, right = height.size() - 1;
    int ans = 0;
    int left_max = 0, right_max = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            height[left] >= left_max ? (left_max = height[left]) : ans += (left_max - height[left]);
            ++left;
        }
        else {
            height[right] >= right_max ? (right_max = height[right]) : ans += (right_max - height[right]);
            --right;
        }
    }
    return ans;
}