本文為senlie原創(chuàng)，轉(zhuǎn)載請保留此地址：http://blog.csdn.net/zhengsenlie
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.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
題意：有一個代表 n 根柱子高度的數(shù)組A[i]，計算這些柱子之間的槽能夠儲蓄的最大水量
思路：左右 dp
用一個數(shù)組 left[i] 表示第 i 根柱子左邊最高的柱子的高度
用一個數(shù)組 right[i] 表示第 i 根柱子右邊最高的柱子的高度
1.從左到右掃描，left[i] = max(left[i - 1], A[i - 1])
2.從右到左掃描，right[i] = max(right[i + 1], A[i + 1])
3.第 i 根柱子上能儲蓄的水為 min(left[i], right[i]) - A[i]，因為這時 left[i] 已經(jīng)沒用了，可以用它來存放這個值。
復(fù)雜度：時間O(n)， 空間O(n)
相關(guān)題目：
Candy
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請聯(lián)系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權(quán)所有
