LeetCode 面试题 17.21. 直方图的水量（双指针）

题目

思路

可以采用双指针解法，一个可以存水的区域水平线必然是这个区域左边或者右边，从左边数定义left指针确定一个边，遇到比left高的则表明这是一个可以存水的区域。

如果只从左边找的话，如果最高的点在中间那么到了这个最高的点就找不到比它低的点了，所以应该先找到最高的点，然后左边找一遍找到最高点，右边找一遍找到最高点，所有的可以存水的区域就都有了。

可以用一个栈把每个可以存水的区域存起来，然后再求这个区域的水量，但是这样比较慢。 当我们从左边找的时候，找的是比left高的地方i为一个区域，所以left比i要低，所以水平面一定是left，那么就可以在寻找的时候就加上水量res = height[left] - height[i]。 然后再从右边找一遍就OK了。

代码语言：javascript复制

class Solution {
public:
    int trap(vector<int>& height) {
        vector<int> arr;
        int res = 0, left = 0, right = height.size() - 1, nmax = 0;
        for (int i = 0; i < height.size(); i  ) {
            if (height[nmax] < height[i]) {
                nmax = i;
            }
        }
        for (int i = 0; i < nmax; i  ) {
            if (height[left] != 0 && left != i && height[left] >= height[i]) {
                res  = height[left] - height[i];
            }
            else {
                left = i;
            }
        }
        for (int i = height.size() - 1; i > nmax; i--) {
            if (height[right] != 0 && left != i && height[right] >= height[i]) {
                res  = height[right] - height[i];
            }
            else {
                right = i;
            }
        }
        return res;
    }
};

height 指针

0 人点赞