题解 | #接雨水问题#

接雨水问题

https://www.nowcoder.com/practice/31c1aed01b394f0b8b7734de0324e00f

方法:双指针

  • step 1:检查数组是否为空的特殊情况
  • step 2:准备双指针,分别指向数组首尾元素,代表最初的两个边界
  • step 3:指针往中间遍历,遇到更低柱子就是底,用较短的边界减去底就是这一列的接水量,遇到更高的柱子就是新的边界,更新边界大小。

时间复杂度:o(n)

空间复杂度:o(1)

class Solution {
  public:
    long long maxWater(vector<int>& arr) {
        // 特殊情况处理
        if (arr.size() == 0)
            return 0;

        long long res = 0;
        int left = 0;
        int right = arr.size() - 1;

        int maxL = 0;
        int maxR = 0;

        while (left < right) {
            maxL = max(maxL, arr[left]);
            maxR = max(maxR, arr[right]);

            if (maxL < maxR)
                res += (maxL - arr[left++]);
            else
                res += (maxR - arr[right--]);
        }

        return res;
    }
};

刷题题解(c++) 文章被收录于专栏

算法题题解(c++)

全部评论

相关推荐

让资本家给我当牛做马:26的秋招还没开始啊?你找的是实习?实习的话你马上就研三了为什么还要实习?
点赞 评论 收藏
分享
牛客刘北:如果暑期实习是27届的话,你要晚一年才会毕业,企业为什么会等你呢?要搞清时间逻辑呀!27届现在实习只能是在暑假实习,这是日常实习,不是暑期实习。所以多去投日常实习吧,暑期实习肯定不会要你的
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务