每日两题 T15

合一大师

发布于 2020-07-20 09:42:53

2730

发布于 2020-07-20 09:42:53

文章被收录于专栏：JavaScript全栈JavaScript全栈

算法

LeetCode T42. 接雨水[1]

描述

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

前端

让一个 div 水平垂直居中

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

References

[1] 42. 接雨水: https://leetcode-cn.com/problems/trapping-rain-water/

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-04-04，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自 JavaScript全栈微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度