## algorithm

### description

Given n non-negative integers representing the height map of each column with a width of 1, calculate how much rain water can be received by the columns arranged in this way.

The above is the height map represented by the array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain (blue Part means rain). Thanks to Marcos for contributing this picture.

Example 1

```Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6```

### analysis

Method 1: Use the stack

We maintain a stack while traversing the array. If the current bar is less than or equal to the bar at the top of the stack, we put the index of the bar on the stack, which means that the current bar is bounded by the previous bar in the stack. If we find that a bar is longer than the top of the stack, we can determine that the bar at the top of the stack is bounded by the current bar and the previous bar of the stack, so we can pop the top element of the stack and accumulate the answer to ans.

Method two: double pointer

From the schematic diagram of the dynamic programming method, we notice that as long as right_max[i]>left_max[i] (element 0 to element 6), the height of the pool will be determined by left_max, similarly left_max[i]>right_max[i] (element 8 To element 11). So we can think that if there is a taller bar at one end (such as the right end), the height of the stagnant water depends on the height in the current direction (from left to right). When we find that the height of the bar on the other side (right side) is not the highest, we start to traverse in the opposite direction (from right to left). We must maintain left_max and }right_max during the traversal, but we can now use two pointers to alternate and achieve 1 traversal to complete.

### Code

Method 1: Use the stack

```/**
* @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;
};```

Method two: double pointer

```/**
* @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;
};```

## front end

### Center a div horizontally and vertically

`flex` layout

```div.parent {
display: flex;
justify-content: center;
align-items: center;
}```

Positioning

```div.parent {
position: relative;
}
div.child {
position: absolute;
top: 50%;
left: 50%;
transform: translate(-50%, -50%);
}
/* or */
div.child {
width: 50px;
height: 10px;
position: absolute;
top: 50%;
left: 50%;
margin-left: -25px;
margin-top: -5px;
}
/* or */
div.child {
width: 50px;
height: 10px;
position: absolute;
left: 0;
top: 0;
right: 0;
bottom: 0;
margin: auto;
}```

grid layout

```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;
}```

``42. Receiving rainwater: https://leetcode-cn.com/problems/trapping-rain-water/