前言
新的一年，好好学习。
正文
问题来源
本问题来自leetcode上的42题。
问题描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
分析：
解法一
通过分别计算每一坐标i上有多少水，进而将其相加得到答案。
问题是我们如何知道每一坐标i上有多少水呢？仔细思考，其实只有出现“两高夹一矮”才可能会存到水。
当 min{ left_most, right_most} 小于或等于其自身高度时，它能存的水就是0，比如array[1]=1,其left_most= array[0]=0, 其right_most=array[7]=3, min{left_most, right_most}=left_most=0< height= array[1]=1，这也就是说坐标1 存不了水。
当min{ left_most,right_most} 大于其自身高度时，这时这三者间出现了“两高夹一矮”的情况，故其能存水，而且其存水数= min{left_most,right_most} - height。
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func trap(height []int) int {
lh := len(height)
var leftMost, rightMost int
total := 0
for i := 1; i < lh - 1; i++ {
leftMost, rightMost = 0, 0
for j := i - 1; j >= 0; j-- {
leftMost = max(leftMost, height[j])
}
for j := i + 1; j < lh; j++ {
rightMost = max(rightMost, height[j])
}
t := min(leftMost, rightMost) - height[i]
if t > 0 {
total += t
}
}
return total
}
解法二
在solution 1里，我们已经知道只要求出left_most和right_most，就可以求出答案，那能不能优化一下求这两个数的过程呢？当然是可以的，我们只需要左遍历一次数组，右遍历一次数组，即可得到left_most和right_most。
int trap(vector<int>& height)
{
if(height == null)
return 0;
int ans = 0;
int size = height.size();
vector<int> left_max(size), right_max(size);
left_max[0] = height[0];
for (int i = 1; i < size; i++) {
left_max[i] = max(height[i], left_max[i - 1]);
}
right_max[size - 1] = height[size - 1];
for (int i = size - 2; i >= 0; i--) {
right_max[i] = max(height[i], right_max[i + 1]);
}
for (int i = 1; i < size - 1; i++) {
ans += min(left_max[i], right_max[i]) - height[i];
}
return ans;
}
解法三
这里再介绍一种优化方法，双指针法，在数组首尾分别创建一个指针，两指针相见时结束循环。
int trap(vector<int>& height)
{
int left = 0, right = height.size() - 1;
int ans = 0;
int left_max = 0, right_max = 0;
while (left < right) {
if (height[left] < height[right]) {
height[left] >= left_max ? (left_max = height[left]) : ans += (left_max - height[left]);
++left;
}
else {
height[right] >= right_max ? (right_max = height[right]) : ans += (right_max - height[right]);
--right;
}
}
return ans;
}
解法四
这是在leetcode中solution给出的一种很新颖的解法，利用了栈的结构，通过维护一个非递增栈来得到答案。
本质思想还是利用了要存水必须是“两高夹一矮”这个特点，只不过这里是用非递增栈来实现。
下面定义一些符号以便理解：
stack[-1] 栈顶元素
stack[-2] 栈顶的下面一个元素（即倒数第二个元素）
solution4的整个算法是这么实现的：遍历数组，遇到一个元素时，将其与栈顶元素比较，如果其小于等于栈顶元素，直接压栈，将其放入栈中（为维护非递增栈的结构,不能将比栈顶元素大的元素压栈），若是其大于栈顶元素，此时一定形成了一个“两高夹一矮”局面，因为栈是非递增栈，所以 stack[-1]<stack[-2],又 current>stack[-1],所以是一个“两高夹一矮”局面，此时算完存水数后栈顶元素出栈，继续判断，递归处理即可。
int trap(vector<int>& height)
{
int ans = 0, current = 0;
stack<int> st;
while (current < height.size()) {
while (!st.empty() && height[current] > height[st.top()]) {
int top = st.top();
st.pop();
if (st.empty())
break;
int distance = current - st.top() - 1;
int bounded_height = min(height[current], height[st.top()]) - height[top];
ans += distance * bounded_height;
}
st.push(current++);
}
return ans;
}
总结：
勤思考。
结语
不管怎么样好好加油。
