接雨水问题(C++)

    xiaoxiao2021-12-15  42

    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.

    翻译:

    给出 n 个非负整数,代表一张X轴上每个区域宽度为 1 的海拔图, 计算这个海拔图最多能接住多少(面积)雨水。

    例如,

    给出 [0,1,0,2,1,0,1,3,2,1,2,1], 返回6

    如下图:

    我的思路是这样的:先设上面的数组为A,先找出整个数组中的最大值,上面的例子中是第八个数,也就是A[7],大小为3。然后以这个值为基准,计算这个值左边的雨水存量,可以找出这个值左边的最大值为A[3],大小为2。这个时候你可以知道,A[3]到A[7]之间的存水量为A[4]到A[7]之间的空间,减去实心部分:(7 - 3 - 1)* A[3] - A[4] - A[5] - A[6] = 4。然后在以A[3]为基准,求左边的存水量,就是一个递归。可以得出左边的存水量为5。同样的道理:右边存水量为1。最后的存水量为5 + 1 = 6。

    写代码的时候为了方便思考,我把求左边的存水来那个和

    class Solution { public: int trap(vector<int>& height) { int len = height.size(); int max = 0; int maxindex = -1; int water = 0; int begin = 0; int end = len - 1; for (int i = 0; i < len; i++) {//获取数组的最高值 if (max < height[i]) { max = height[i]; maxindex = i; } } water = water + leftpartialwater(height, begin, maxindex, max);//计算最高值左边的雨水量 water = water + rightpartialwater(height, maxindex, end, max);//计算最高值右边的雨水量 return water; } int leftpartialwater(vector<int> &heights, int begin, int end, int max) {//计算左边的存水量 int curwater = 0; if (begin >= end) { curwater = 0; } else { int curmax = 0; int curmaxindex = -1; for (int i = begin; i < end; i++) {//查找最大值左边的其他元素的最大值 if (curmax <= heights[i]) { curmax = heights[i]; curmaxindex = i; } } curwater = (end - curmaxindex - 1) * curmax; int other = 0; for (int j = curmaxindex + 1; j < end; j++) { other = other + heights[j]; } curwater = curwater - other;//计算之前的最大值到当前求出的最大值之间的存水量 curwater = curwater + leftpartialwater(heights, begin, curmaxindex, curmax);//递归,求当前的最大值到下一个最大值之间的存水量 } return curwater; } int rightpartialwater(vector<int> &heights, int begin, int end, int max) {//计算右边的存水量 int curwater = 0; if (begin >= end) { curwater = 0; } else { int curmax = 0; int curmaxindex = - 1; for (int i = begin + 1; i <= end; i++) {//查找最大值右边的其他元素的最大值 if (curmax <= heights[i]) { curmax = heights[i]; curmaxindex = i; } } curwater = (curmaxindex- begin - 1) * curmax; int other = 0; for (int j = begin + 1; j < curmaxindex; j++) { other = other + heights[j]; } curwater = curwater - other;//计算之前的最大值到当前求出的最大值之间的存水量 curwater = curwater + rightpartialwater(heights, curmaxindex, end, curmax);//递归,求当前的最大值到下一个最大值之间的存水量 } return curwater; } };要是大家还有什么高见,请指教啊。

    转载请注明原文地址: https://ju.6miu.com/read-1000387.html

    最新回复(0)