给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。感谢 Marcos 贡献此图。
示例1
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
方法一:使用栈
我们在遍历数组时维护一个栈。如果当前的条形块小于或等于栈顶的条形块,我们将条形块的索引入栈,意思是当前的条形块被栈中的前一个条形块界定。如果我们发现一个条形块长于栈顶,我们可以确定栈顶的条形块被当前条形块和栈的前一个条形块界定,因此我们可以弹出栈顶元素并且累加答案到 ans 。
方法二:双指针
从动态编程方法的示意图中我们注意到,只要 right_max[i]>left_max[i] (元素 0 到元素 6),积水高度将由 left_max 决定,类似地 left_max[i]>right_max[i](元素 8 到元素 11)。所以我们可以认为如果一端有更高的条形块(例如右端),积水的高度依赖于当前方向的高度(从左到右)。当我们发现另一侧(右侧)的条形块高度不是最高的,我们则开始从相反的方向遍历(从右到左)。我们必须在遍历时维护 left_max 和 }right_max ,但是我们现在可以使用两个指针交替进行,实现 1 次遍历即可完成。
方法一:使用栈
/**
* @param {number[]} height
* @return {number}
*/
var trap = function (height) {
let ans = 0, current = 0;
const st = [];
while (current < height.length) {
while ((st.length !== 0) && (height[current] > height[st[st.length - 1]])) {
let top = st.pop();
if (st.length === 0)
break;
let distance = current - st[st.length - 1] - 1;
let bounded_height = Math.min(height[current], height[st[st.length - 1]]) - height[top];
ans += distance * bounded_height;
}
st.push(current++);
}
return ans;
};
方法二:双指针
/**
* @param {number[]} height
* @return {number}
*/
var trap = function (height) {
let left = 0, right = height.length - 1;
let ans = 0;
let 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;
};
flex
布局
div.parent {
display: flex;
justify-content: center;
align-items: center;
}
定位
div.parent {
position: relative;
}
div.child {
position: absolute;
top: 50%;
left: 50%;
transform: translate(-50%, -50%);
}
/* 或者 */
div.child {
width: 50px;
height: 10px;
position: absolute;
top: 50%;
left: 50%;
margin-left: -25px;
margin-top: -5px;
}
/* 或 */
div.child {
width: 50px;
height: 10px;
position: absolute;
left: 0;
top: 0;
right: 0;
bottom: 0;
margin: auto;
}
grid布局
div.parent {
display: grid;
}
div.child {
justify-self: center;
align-self: center;
}
Inline-block
div.parent {
font-size: 0;
text-align: center;
&::before {
content: "";
display: inline-block;
width: 0;
height: 100%;
vertical-align: middle;
}
}
div.child{
display: inline-block;
vertical-align: middle;
}
table
div.parent {
display: table;
}
div.child {
display: table-cell
vertical-align: middle;
text-align: center;
}
[1]
42. 接雨水: https://leetcode-cn.com/problems/trapping-rain-water/
本文分享自 JavaScript全栈 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!