接雨水（leetcode_42）
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [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
关于这题我自己想到的思路是，先找到最高的那个柱子，然后向下一层一层遍历，每层的水数为最左最右两边的此处有柱子的坐标的差距减去中间的柱子数。
class Solution
{
public:
int trap(vector<int> &height)
{
int size = height.size();
if (size <= 1)
return 0;
int max_height = *max_element(height.begin(), height.end());
int total = 0;
int x;
for (int current_height = max_height; current_height > 0; --current_height)
{
x = 0;
for (int i = 0; i < size; ++i)
{
if (height[i] >= current_height)
{
x = i;
break;
}
}
for (int i = x + 1; i < size; ++i)
{
if (height[i] >= current_height)
{
total += (i - x - 1);
x = i;
}
}
}
return total;
}
};
这题虽然能解决这个问题，但是太复杂，最后不能通过最后一个测试样例，那个测试样例有10730个，好像，每个柱子的高度不统一，有的是几万，有的只有几十。这样算下来，最后循环次数过多，（几万乘几万最后得遍历几亿次）。
官方题解我觉得比较好接受的有两种方法，一个是动态分析法。一个是双指针法。
动态分析法，我觉得就是对物理世界的模拟，简单来说，某个柱子处最高有多长的水柱取决于该柱子两侧最高的两个柱子的最低高度，这样来说，我们只要遍历两边这个柱子高度序列就可以知道left_max和right_max。得到这样的数组之后我们就可以在遍历一遍得到最终的total了
class Solution_pro
{
public:
int trap(vector<int> &height)
{
if (height.empty())
return 0;
int total = 0;
int size = height.size();
int max_left[size], max_right[size];
max_left[0] = height[0];
for (int i = 1; i < size; ++i)
{
max_left[i] = max(height[i], max_left[i - 1]);
}
max_right[size - 1] = height[size - 1];
for (int j = size - 2; j > 0; --j)
{
max_right[j] = max(height[j], max_right[j + 1]);
}
for (int i = 1; i < size - 1; ++i)
{
total += min(max_left[i], max_right[i]) - height[i];
}
return total;
}
};
双指针法我觉得我不太可能想的出来，这个算法有点骚。
官方的解释是
我们可以认为如果一端有更高的条形块（例如右端），积水的高度依赖于当前方向的高度（从左到右）。当我们发现另一侧（右侧）的条形块高度不是最高的，我们则开始从相反的方向遍历（从右到左）。我们必须在遍历时维护 left_max 和 right_max ，但是我们现在可以使用两个指针交替进行，实现 1 次遍历即可完成。
我个人的理解是，由于水柱的长度取决于当前左右两边最高的两个中较小的那个，我们只要每次比较left和right指向的元素，然后移动right和left指针，根据比较的结果，判断当前元素和最左（右）最大的元素的大小，从而判断出水柱的高度。
我开始有一个疑问，就是我每次比较的是当前的left和right指针指向的水柱元素，但是当left的左边有比当前水柱更高的元素时，那不就是可能存在更高的水柱了么。
但是仔细分析一下，我们可以知道，left指向当前元素的前提是上一个left也还是比当前right小，从而最极端的情况下最左的所有left都比当前right小，这样每次水柱的高度就完全取决的左边的元素了。
class Solution_pro_max
{
public:
int trap(vector<int> &height)
{
if (height.empty())
return 0;
int total = 0;
int left = 0;
int right = height.size() - 1;
int left_max = 0, right_max = 0;
while (left < right)
{
if (height[left] < height[right])
{
left_max >= height[left] ? (total += (left_max - height[left])) : (left_max = height[left]);//这种写法我在上一篇博客中介绍过。
left++;
}
else
{
right_max >= height[right] ? (total += (right_max - height[right])) : (right_max = height[right]);
right--;
}
}
return total;
}
};