面试题17.21.直方图的水量

链接：面试题17.21.直方图的水量
难度：Hard
标签：栈、数组、双指针、动态规划、单调栈
简介：给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。

题解 1 - typescript

• 编辑时间：2021-04-02
• 执行用时：112ms
• 内存消耗：39.8MB
• 编程语言：typescript
• 解法介绍：优化题解 1，取消右数组。

function trap(height: number[]): number {
  let max = 0;
  const len = height.length;
  const left: number[] = [0];
  for (let i = 1; i < len; i++) left.push((max = Math.max(max, height[i - 1])));
  let ans = 0;
  max = 0;
  for (let i = len - 2; i >= 0; i--) {
    const num = Math.min(left[i], (max = Math.max(max, height[i + 1]))) - height[i];
    ans += num > 0 ? num : 0;
  }
  return ans;
}

题解 2 - typescript

• 编辑时间：2021-04-02
• 执行用时：108ms
• 内存消耗：39.9MB
• 编程语言：typescript
• 解法介绍：求出左右最高高度进行比较。

function trap(height: number[]): number {
  let max = 0;
  const len = height.length;
  const left: number[] = [0];
  for (let i = 1; i < len; i++) left.push((max = Math.max(max, height[i - 1])));
  const right: number[] = [0];
  max = 0;
  for (let i = len - 2; i >= 0; i--) right.unshift((max = Math.max(max, height[i + 1])));
  let ans = 0;
  for (let i = 0; i < len; i++) {
    const num = Math.min(left[i], right[i]) - height[i];
    ans += num > 0 ? num : 0;
  }
  return ans;
}