1、到今天完成39题，还需要不停的加油。今天再分析下装雨水这道题
Given n non-negative integers representing an elevation map where the width
of each bar is 1, compute how much water it is able to trap after raining. For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
思想：将装满水的面积减去没有装水的面积。
rain = water_sum - nowater_sum
有效地计算water_sum是本问题的关键。
2、一个区域的内能够承水是因为形成了由大到小再到大的凹坑。
定义 right_max[0--n-1]，用来保存从右往左搜索得到的最大值。如right_max[i]，表示在i这个柱子，右边的最高柱子值为right_max[i].
同理定义 left_max[0--n-1]
i柱子灌水后的区域面积为min(left_max[i], right_max[i]), 因为短板效应。
如此对0至n-1求此min(i)的和，便得到了water_sum，答案也就轻易得出了。代码如下。
主要思想在于把雨水的问题转化成有水无水的求差。
借助两个矩阵left_max, right_max 保存中间结果，巧妙地减少了许多计算量。
#include "stdafx.h" #include <iostream> using namespace std; class Solution { public: int trap(int A[], int n); }; // Accepted, O(n) int Solution::trap(int A[], int n) { // 注意极端情况的考虑哦！ if(n == 0) return 0; int *right_max = new int[n]; int tmp_max = A[n-1]; right_max[n-1] = A[n-1]; // 没有水时的面积 int nowater_sum = A[n-1]; for(int i = n-2; i >= 0; --i) { if(A[i] > tmp_max) tmp_max = A[i]; right_max[i] = tmp_max; nowater_sum += A[i]; } int *left_max = new int[n]; tmp_max = A[0]; left_max[0] = A[0]; for(int i = 1; i < n; ++i) { if(A[i] > tmp_max) tmp_max = A[i]; left_max[i] = tmp_max; } // 计算有水时的面积 int water_sum = 0; for(int i = 0; i < n; ++i) { water_sum += min(left_max[i], right_max[i]); } delete []right_max; delete []left_max; return water_sum - nowater_sum; } int _tmain(int argc, _TCHAR* argv[]) { int A[12] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}; Solution slu; int result = slu.trap(A, 12); return 0; }