leetcode Trapping Rain Water

浏览数：32 / 时间：2015年06月11日

无脑写代码代码（TLE）：

技术分享 
 1 #include<iostream>
 2 #include<vector>
 3 
 4 using namespace std;
 5 
 6 int findLeft(int i, vector<int> height)
 7 {
 8     int t = i-1;
 9     while ((t+1<height.size())&&t >= 0)
10     {
11         if (height[t] > height[t + 1])
12             t--;
13         else
14             break;
15     }
16     return t + 1;
17 }
18 
19 int findRight(int i, vector<int> height)
20 {
21     int t = i + 1; 
22     while ((t-1>=0)&&t < height.size())
23     {
24         if (height[t] > height[t - 1])
25             t++;
26         else
27             break;
28     }
29     return t - 1;
30 }
31 
32 int trap(vector<int>& height) 
33 {
34     int L = height.size();
35     int sum = 0;
36     for (int i = 1; i < L-1; i++)
37     {
38         int left = findLeft(i, height);
39         int right = findRight(i, height);
40         if (left < i&&right > i)
41         {
42             int high = height[left] < height[right] ? height[left] : height[right];
43             for (int j = left+1; j < right; j++)
44             {
45                 sum = sum + high - height[j];
46             }
47         }
48     }
49     return sum;
50 }
51 
52 int main()
53 {
54     vector<int> height = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
55     cout << trap(height) << endl;
56 }
View Code

 

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： Android iOS 移动互联 终端开发

相关文章

随机文章

您可能还喜欢

您可能还喜欢