[LeetCode] 42. Trapping Rain Water

轉自LeetCode

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!

<Solution>

這題的想法如下

• 因為含水量，一定受限於最低高度，所以先準備兩個指針，一個從左一個從右，看看目前誰的高度比較小，然後再從小的那一方開始找起

• 確認比較小的高度在哪一邊後，舉例左邊，那從 left 指針開始往右找。而要能保存水，一定要遇到一個大於等於目前最低高度的地方，才可能存到水，而能存到水的量，就等於 minHeight - height[left]。從右邊找也是一樣的概念，方向不一樣而已

code 如下
c++

	class Solution {
	public:
	int trap(vector<int>& height) {
	int left = 0, right = height.size() - 1, ans = 0;
	while(left < right) {
	int minH = min(height[left], height[right]);
	//> start from minH to find how much water can be trapped
	if(height[left] == minH) {
	++left;
	while(left < right && height[left] < minH) {
	ans += minH - height[left];
	++left;
	}
	}
	else {
	--right;
	while(left < right && height[right] < minH) {
	ans += minH - height[right];
	--right;
	}
	}
	}
	return ans;
	}
	};

view raw trapWater.cpp hosted with ❤ by GitHub

另一個是使用 stack 的概念來解(參考1, 參考2)

當遇到目前高度 <= stack的top 的時候，就放到 stack 裡面

因為當相鄰兩個高度是遞減的時候，是沒有空間可以儲水的

所以當遇到目前高度 > stack 的 top 的時候，代表找到一個凹朝可以存水

這時候將 stack 的 top 拿出來，然後左右邊界找比較低的那個，乘上距離算出儲水量

這邊要注意，如果將 top 拿出來後， stack 是空的時候

就代表相鄰兩個矩形是遞增的，且前面也沒有矩形了

也是沒辦法儲水，所以就繼續歷遍就好

kotlin

	class Solution {
	fun trap(height: IntArray): Int {
	var ans = 0
	var stack = mutableListOf<Int>()
	var i = 0
	while(i < height.size) {
	if(stack.isEmpty() || height[stack.last()] >= height[i]) {
	stack.add(i)
	++i
	} else {
	val last = stack.last()
	stack.removeAt(stack.lastIndex)
	if(stack.isEmpty()) {
	continue
	}
	ans += (Math.min(height[stack.last()], height[i]) - height[last]) * (i - stack.last() - 1)
	}
	}
	return ans
	}
	}

view raw trapping_rain_water.kt hosted with ❤ by GitHub