首页 > 试题广场 > 给定n个柱面的高度,表示降雨某地n块区域的海拔高度。 计算降
[问答题]
给定n个柱面的高度,表示降雨某地n块区域的海拔高度。
计算降雨之后该地最大储水面积。如果低于地平线,也就是小于0,则一定积水
int trap(vector<int>& height) {
		int n = height.size();
		// left[i]表示i左边的最大值,right[i]表示i右边的最大值
		vector<int> left(n), right(n);
		for (int i = 1; i < n; i++) {
			left[i] = max(left[i - 1], height[i - 1]);
		}
		for (int i = n - 2; i >= 0; i--) {
			right[i] = max(right[i + 1], height[i + 1]);
		}
		int water = 0;
		for (int i = 0; i < n; i++) {
			int level = min(left[i], right[i]);
			water += max(0, level - height[i]);
		}
		return water;
	}


发表于 2019-09-15 10:25:45 回复(0)
这是LeetCode第42题,本质上需要维护一个栈的数据结构,遇到比自己大的数就出栈。
发表于 2019-08-22 13:48:29 回复(0)
#假设n传入为list
#降雨后得到的对应n的list为a

def count_area(n,a):
    result = 0
    for i in range(len(n)):
        result += n[i]-a[i]
        
    return result
发表于 2019-08-14 15:18:13 回复(0)