LeetCode 42. Trapping Rain Water

描述

给出一些柱子的高度，求这些连续柱子所能存储的水的体积

解决

找出最高的柱子，然后遍历左右两边即可

---

class Solution { public: int trap(vector<int>& height) { int length = height.size(); if (length <= 1) return 0; int max_height_index = -1, tmp_heigth = INT_MIN; for (int i = 0; i < length; ++i) { if (height[i] >= tmp_heigth) { tmp_heigth = height[i]; max_height_index = i; } } auto sum = 0, max_val = 0; for (int i = 0; i < max_height_index && i < length - 1; ++i) { if (height[i] > max_val) max_val = height[i]; else sum += max_val - height[i]; } max_val = 0; for (int i = length - 1; i > max_height_index && i > 0; --i) { if (height[i] > max_val) max_val = height[i]; else sum += max_val - height[i]; } return sum; } };