Two questions a day T15

Two questions a day T15

algorithm

LeetCode T42. Receiving rainwater[1]

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

References

[1]42. Receiving rainwater: https://leetcode-cn.com/problems/trapping-rain-water/

Reference: https://cloud.tencent.com/developer/article/1664343 Two questions a day T15-Cloud + Community-Tencent Cloud