leetcode#42接雨水（C语言实现）

题目描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
算法思路一：
对于任意位置i，求出i位置左边数组的最大值，以及i位置右边数组的最大值，显然i位置能装多少水，取决于两个最大值中较小的一个（设这个数为temp），如果temp>height[i]，则i位置可以装水temp-height[i]的水
①使用两个数组left和right数组，left[i]表示i位置左边的最大值，显然有left[i]=max{left[i-1],height[i]}，同理right[i]用来表示i位置右边的最大值，显然有right[i]={right[i+1],height[i]}
②从i=1一直遍历到i=height-2，每个位置的装水的综合即是返回值
时间复杂度O(n)，空间复杂度O(n)
算法实现一：

int trap(int* height, int heightSize){if(heightSize<=2) return 0;int left[heightSize],right[heightSize];int i=0,max=-1,res=0;left[0]=height[0],right[0]=height[0];for(i=1;i<heightSize;i++){left[i]=height[i]>left[i-1]?height[i]:left[i-1];}for(i=heightSize-2;i>=0;i--){right[i]=height[i]>right[i+1]?height[i]:right[i+1];}for(i=1;i<heightSize-1;i++){int min=left[i]>right[i]?right[i]:left[i];res+=min-height[i];}return res;
}

算法思路2：双指针法
使用left=0，right=heightSize-1，同时用rightMax和LeftMax来保存扫描到左右指针位置时的对应最大值。使用循环，两个指针遍历数组，当指针相遇时停止遍历。
因为装水多少是由rightMax和leftMax中更小的值决定的。不失一般性的以left举例：如果leftMax更小，那我们就观察left指针，
①如果height[left]比leftMax小，说明left位置必定可以装水
②反之不能装水，同时更新leftMax的值为height[left]
left位置已经观察过了，所以指针移动left++;
具体算法建议直接看代码，代码实现并不复杂。
时间复杂度O(n)，空间复杂度O(1)
算法实现二

int trap(int* height, int heightSize){if(heightSize<=2) return 0;int left=0,right=heightSize-1;int leftMax=height[0],rightMax=height[heightSize-1];int ans=0;while(left<=right){if(leftMax<rightMax){if(height[left]<leftMax){ans+=leftMax-height[left];}else{leftMax=height[left];}left++;}else{if(height[right]<rightMax){ans+=rightMax-height[right];}else{rightMax=height[right];}right--;}}return ans;
}

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