首页 🍒LeetCode,🐶算法

题目

clbGOWUQiV.png

思路

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

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

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

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;
    }
};



文章评论