42. 接雨水 - 力扣（LeetCode）

三种解决办法   1.双指针法   2. 动态规划   3. 单调栈

1.双指针方法 ：   核心思想是可以从行看或者从列算面积但是核心必须掌握一个必须是一直按照一个方向进行计算否则很容易错误我们假如按照列计算规定行宽度为 1

那么如何计算列高度呢 ？  我们就是左侧最高柱子和右侧最高柱子之间最小的柱子高度减去当前所在的高度 就是承接雨水的高度  max（left，right）-height[i];

class Solution {
public:int trap(vector& height) { int sum = 0;int n = height.size();for(int i = 0;i=0;l--) {left = max(left,height[l]);}int h = min(left,right)-height[i];if(h > 0) {sum+=h;}}return sum;}
};

这种办法时间复杂度是平方级别所以会产生超出时间限制 那么有没有什么办法可以把时间复杂度降低呢？

 我们可以思考一下 为什么时间复杂度是平方？ 因为每一次到每个行位置都需要去遍历（分别 向左向右遍历）整个数组去找当前行的左面最大高度 和右面最大高度 那么我们可以去尝试使用空间换时间的方法去提前准备好(把左面最大高度和右面最大高度)用数组存储起来也就是前缀和的一种思想

class Solution {
public:int trap(vector& height) {int n=height.size();int res=0;vectorle(n),ri(n);//数组le[0]=height[0];for(int i=1;i=0;j--) {ri[j]=max(ri[j+1],height[j]);//右面的最大值}for(int i=1;i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！