Leetcode 42接雨水（从暴力开始优化，难度偏大）

 如果一开始就想双指针之类O(N)的算法是很困难的，先想想最暴力的做法：

单独计算每一个位置可以接多少水？每次单独向左向右遍历：先找到左边和右边的最大值，在取最小值即可。时间复杂度是O(N^2)

class Solution { public: int trap(vector<int>& height) { // 统计每一个格子可以解多少雨水 int n = height.size(), res = 0; for(int i=1;i<n;i++){ int leftmax = 0, rightmax = 0; for(int j=i;j>=0;j--) leftmax = max(leftmax,height[j]); for(int j=i;j<n;j++) rightmax = max(rightmax,height[j]); res+=min(leftmax,rightmax) - height[i]; } return res; } };

怎么优化，很简单，空间换时间，先遍历一遍，预处理每一个格点左边和右边的最大值的最小值，然后再来做，这样就能把时间复杂度优化到O(N）

class Solution { public: int trap(vector<int>& height) { int n = height.size(), res = 0; vector<int> maxLeftHeight(n,0), maxRightHeight(n,0); int maxLeft=0, maxRight=0; for(int i=0;i<n;i++) { maxLeftHeight[i] = max(maxLeft, height[i]); maxLeft = max(maxLeft,height[i]); } for(int i=n-1;i>=0;i--){ maxRightHeight[i] = max(maxRight, height[i]); maxRight = max(maxRight,height[i]); } for(int i=0;i<n;i++) res+=(min(maxLeftHeight[i],maxRightHeight[i])-height[i]); return res; } };