题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
题解
几乎一次过,受宠若惊啊哈哈哈哈
感觉没啥难的地方啊,就看图写代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
| int trap(vector<int>& height) { int res = 0; int vsize = height.size(); if (vsize < 3)return 0; while (height[0] <= height[1]) { height.erase(height.begin()); vsize--; if (vsize < 3)return 0; } while (height[vsize - 1] <= height[vsize - 2]) { height.erase(height.end() - 1); vsize--; if (vsize < 3)return 0; } int t1 = 0; int t2 = t1 + 1; while (t2<vsize) { int h_sum = 0; while (t2 < vsize&&height[t2] < height[t1]) { h_sum += height[t2]; t2++; } if (t2 < vsize) { if (t2 - t2>1) res = res + height[t1] * (t2 - t1 - 1) - h_sum; t1 = t2; } t2++; } int limit = t1; t1 = vsize - 1; t2 = t1 - 1; while (t2 >= limit) { int h_sum = 0; while (t2 >= limit && height[t2] < height[t1]) { h_sum += height[t2]; t2--; } if (t2 >= limit) { if(t1 - t2>1) res = res + height[t1] * (t1 - t2 - 1) - h_sum; t1 = t2; } t2--; } return res; }
|