leetcode 42 接雨水

leetcode 42 接雨水 两种解法

第一次遇到这个题目是在数据结构课题目里面完全不会写，上leetcode找到了双指针你的写法，后来又找到此题回顾。

解法1 暴力解法

能存下雨水，说明雨水左右的高度都是大于雨水的高度的，因此我们只需要找到每个空位左右分别哪个最高就好了。

class Solution {
public:int trap(vector<int>& height) {int left_max = 0,right_max = 0;int sum = 0;int n = height.size();for(int i = 0;i<n-1;i++){int left_max,right_max;left_max = 0;right_max = 0;for(int j = i;j>=0;j--){if(height[j]>left_max)left_max = height[j];}for(int j = i;j<n;j++){if(height[j]>right_max)right_max = height[j];}sum+= min(right_max,left_max)-height[i];}return sum;}
};

时间复杂度为O(n^2) 空间复杂度为O(1)

解法2 韦恩图法

class Solution {
public:int trap(vector<int>& height) {int n = height.size();int max1,max2,s1,s2;max1 = 0,max2 = 0;s1 = 0,s2 = 0;for(int i = 0;i<n;++i ){if(height[i]>max1)    max1 = height[i];if(height[n-i-1] > max2)max2 = height[n-i-1];s1+=max1;s2+=max2;}int sum = accumulate(height.begin(),height.end(),0); //快速求和return s1+s2 - n * max1 - sum;}
};

建议画图理解这个重复片段刚好就是能积雨水的大小。
另外还有双指针解法。

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