高端网站建设 aspx,廊坊做网站企业教程,站长工具app下载,wordpress 农家乐给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。
示例 1#xff1a; 输入#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1]
输出#xff1a;6
解释#xff1a;上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] …给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。
示例 1 输入height [0,1,0,2,1,0,1,3,2,1,2,1]
输出6
解释上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图在这种情况下可以接 6 个单位的雨水蓝色部分表示雨水。 示例 2
输入height [4,2,0,3,2,5]
输出9提示
n height.length1 n 2 * 1040 height[i] 105
题解
这道题是双指针里面困难级别的题
我一开始的想法是用两个指针分别从左右两边出发两边都是判断当前木板的高度是否低于先前碰到的最高的木板如果是那么累加二者的高度差这样的思路基于一个前提前面存在更高木板可以把水给罩住
但是存在一种情况那就是一开始碰到的木板就是最高的所以这种思路不行
官方给的思路是左右两边都计算一次然后取二者间最小的 我在实现官方的思路的时候想到了一种新的方法一开始就去找到最高的那个木板所在的地方仍然从左右两边出发去计算但是碰到最高的地方我就停下来不算了
完美解决 class Solution {
public:int trap(vectorint height) {int highest 0;for (int i 0; i height.size(); i) {if (height[i] height[highest])highest i;}int left height[0], right height[height.size() - 1], drop 0, i 1, j height.size() - 2;while (i highest) {if (height[i] left) {drop left - height[i];} else {left height[i];}i;}while (jhighest) {if (height[j] right) {drop right - height[j];} else {right height[j];}j--;}return drop;}
};
