Loading...
墨滴

SuperMP

2021/04/20  阅读:49  主题:默认主题

Leetcode刷题 | 第115题:直方图的水量

起风了,唯有努力生存。

面试题 17.21. 直方图的水量[1] (困难)

题目:给定一个直方图(也称柱状图),假设有人从上面源源不断地倒水,最后直方图能存多少水量?直方图的宽度为 1。 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图,在这种情况下,可以接 6 个单位的水(蓝色部分表示水)。

输入: [0,1,0,2,1,0,1,3,2,1,2,1], 输出: 6

相似题目:Leetcode刷题 | 第103题:盛最多水的容器


分析1每个柱子所存储的水量由其左、右两侧的柱子的最大高度中的较矮者决定。例如,示例中索引 2 / 6 存储的水量为 1 / 1,其计算过程为:

  • 首先计算其索引位置两侧的柱子的最大高度:其左侧为 1 / 2 ,其右侧为 3 / 3,较矮者为 1 / 2,因此存水量为较矮者的高度与该索引位置的高度之差,即 1 - 0 = 0 / 2 - 1 = 1。

因此,为了计算直方图的水量:

  1. 需要记录每个柱子左、右两侧的所有柱子的最大高度;
  2. 利用步骤 1 的结果,计算每个柱子的存水量(即,较矮者的高度与该索引位置的高度之差),并求和。

Java代码:(动态规划)

class Solution {
    public int trap(int[] barGraph) {
        int n = barGraph.length;
        if (n == 0return 0;

        int[] leftMaxValArr = new int[n]; // 每个柱子左侧的所有柱子的最大高度
        int[] rightMaxValArr = new int[n]; // 每个柱子右侧的所有柱子的最大高度
        leftMaxValArr[0] = barGraph[0];
        rightMaxValArr[n - 1] = barGraph[n - 1];
        
        for (int i = 1; i < n; i++) {
            leftMaxValArr[i] = Math.max(barGraph[i], leftMaxValArr[i - 1]);
            rightMaxValArr[n - 1 - i] = Math.max(barGraph[n - 1 - i], rightMaxValArr[n - i]);
        }
        // System.out.println(Arrays.toString(leftMaxValArr));
        // System.out.println(Arrays.toString(rightMaxValArr));
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += Math.min(leftMaxValArr[i], rightMaxValArr[i]) - barGraph[i];
        }
        return ans;
    }
}
  • 时间复杂度为 O(N),空间复杂度为 O(N)。

分析2:每个柱子所存储的水量由其左、右两侧的柱子的最大高度中的较矮者决定。单纯地就每一个柱子来看:

  • 如果该柱子左侧的最大高度的柱子 A 较矮,那么其能够存储的水量为 A 的高度 - 该索引位置的柱子的高度。这是因为右侧有比左侧最大高度的柱子 A 还要高的柱子能够将水 “装起来”
  • 如果该柱子右侧的最大高度的柱子 B 较矮,那么其能够存储的水量为 B 的高度 - 该索引位置的柱子的高度。这是因为左侧有比右侧最大高度的柱子 B 还要高的柱子能够将水 “装起来”。

因此,可以利用双指针进行实现:当左侧较矮时,计算左指针位置能够存储的水量;反之计算右指针位置能够存储的水量。

Java代码:(双指针)

class Solution {
    public int trap(int[] barGraph) {
        int l = 0, r = barGraph.length - 1, ans = 0;
        int leftMax = 0, rightMax = 0;
        while (l < r) {
            leftMax = Math.max(leftMax, barGraph[l]);
            rightMax = Math.max(rightMax, barGraph[r]);
            ans += leftMax < rightMax ? leftMax - barGraph[l++] : rightMax - barGraph[r--];
        }
        return ans;
    }
}
  • 时间复杂度为 O(N),空间复杂度为 O(1)。

另一种思路:利用单调栈。

参考资料

[1]

直方图的水量: https://leetcode-cn.com/problems/volume-of-histogram-lcci/

SuperMP

2021/04/20  阅读:49  主题:默认主题

作者介绍

SuperMP