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; }
