[LeetCode] Trapping Rain Water

题目描述

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.



The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

解法一

使用栈

这个题和Largest Rectangle In Histogram那个题很相似。凹陷处可以积水。所以寻找先递减后递增的位置就可以了。由于积水量只有在递增时才能计算,计算时需要用到递减序列中的bar的高度。需要将递减序列保存。使用stack。为了便于面积计算中宽度的计算,stack存放的不是递减序列bar的高度,而是每个bar的坐标。

// use stack
int trap(int A[], int n) {
    stack<int> s;
    int water = 0;
    s.push(0);
    for (int i = 1; i < n; i++) {
        if (A[i] > A[s.top()]) {
            int bottom = A[s.top()];
            s.pop();
            // A[i] is right highest bar
            while (!s.empty() && A[i]>=A[s.top()]) {
                int height = A[s.top()] - bottom;
                int width = i - s.top() - 1;
                water += height * width;
                bottom = A[s.top()];
                s.pop();
            }
            // stack top is left highest bar
            if (!s.empty()) water += (A[i] - bottom) * (i - s.top() - 1);
        }
        s.push(i);
    }
    return water;
}

解法二

如果一个一个bar看,那么每个bar的存水量肯定是取左端最高的bar和右端最高bar两者中的最小值,这个很好想,然后先用两个数组把leftHighest和rightHighest保存下来,然后再遍历bar的高度进行计算

// use extra space
int trap(int A[], int n) {
    int leftHighest[n], rightHighest[n], maxh;
    leftHighest[0] = 0, maxh = 0;
    for (int i = 1; i < n; i++)
        leftHighest[i] = maxh = max(maxh, A[i - 1]);
    rightHighest[n - 1] = 0, maxh = 0;
    for (int i = n - 2; i >= 0; i--)
        rightHighest[i] = maxh = max(maxh, A[i + 1]);
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += max(0, min(leftHighest[i], rightHighest[i]) - A[i]);
    return sum;
}

进一步简化

这个方法很巧妙,maxh始终是存的某个bar另一端(如果bar是左边的,那maxh就是右边的)的一个较高值,下面计算每个area的那一步可以写成

area += max(maxh - lw, 0);

这样可能稍微好懂一点,如果另一边有比他高的,能存,就是 maxh - lw(或者 maxh - rw ),要么就是一样,就是0,不能存水。因为总是取左边和右边的最小值,肯定是不会出现负值的。如果一样的话,肯定会有一个指针移动,然后再去寻找比那个低bar高的bar,还会出现前面的场景。

// use no extra space
int trap(int A[], int n) {
    int area = 0;
    int maxh = 0;
    int left = 0, right = n-1;
    while (left < right) {
        // if can not contain water
        int lw = A[left], rw = A[right];
        if (lw < rw) {
            maxh = max(maxh, lw);
            area += maxh - lw;
            left++;
        }
        else {
            maxh = max(maxh, rw);
            area += maxh - rw;
            right--;
        }

    }
    return area;
}