22
Leetcode 42 接雨水 双指针
source link: http://www.cnblogs.com/itdef/p/12077321.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
地址 https://leetcode-cn.com/problems/trapping-rain-water/
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例: 输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6
解答
暴力遍历的时候
如果起点较低的一端 那么遇到较高的一端 就可以计算盛水体积
但是如果起点是较高的一端 就不好确定终点。
使用双指针确定盛水段落的左右断点
如果左边较低就从左边开始寻找比他等于或者大于的终点
如果右边较低就从右边开始寻找等于或者大于的终点
代码如下
1 class Solution {
2 public:
3 int trap(vector<int>& height) {
4 int ret = 0;
5 int l =0;int r = height.size()-1;
6 while(l < r){
7 int mn = min(height[l],height[r]);
8 if(mn == height[l]){
9 l++;
10 while(l<r && height[l] < mn){
11 ret += mn-height[l];
12 l++;
13 }
14
15 }else{
16 r--;
17 while(l<r && height[r]<mn){
18 ret += mn-height[r];
19 r--;
20 }
21 }
22 }
23
24 return ret;
25 }
26 };
View Code
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK