网站程序开发教程,wordpress 折800模板,付费ppt模板网站哪个好,机械行业做网站1 题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。
2 思路
这个题主要是要清楚, 接的最多的雨水总量为一个位置的最高水位减去这个位置的高度(也就是该位置的接水量)的总和, 而每一个位置的最高水…1 题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。
2 思路
这个题主要是要清楚, 接的最多的雨水总量为一个位置的最高水位减去这个位置的高度(也就是该位置的接水量)的总和, 而每一个位置的最高水位是其左边最高高度以及其右边最高高度两者取其小. 现在的问题变成了怎么确定每一个位置的左边最高高度和右边最高高度. 用动态规划的方法来确定.
代码:
int trap(vectorint height) {int height_size height.size();int total 0;if (height_size 2) {vectorint left_max(height_size, 0);vectorint right_max(height_size, 0);left_max[0] height[0];right_max[height_size - 1] height[height_size - 1];for (int i 1; i height_size; i ) {left_max[i] max(left_max[i - 1], height[i]);}for (int i height_size - 2; i 0; i --) {right_max[i] max(right_max[i 1], height[i]);total min(left_max[i], right_max[i]) - height[i];}}return total;
}
