题目概述:给定一些柱子的高度,问这些柱子能够接到多少雨水
解题思路:将每个位置都想象有一个木桶,接到雨水的量=木桶体积-柱子体积。木桶的高度由前后缀数组中的较小者决定
时间复杂度:\(O(n)\)
代码:
class Solution {
public int trap(int[] height) {
int n = height.length;
int pre[] = new int[n];
int suf[] = new int[n];
pre[0] = height[0];
suf[n - 1] = height[n - 1];
for(int i = 1; i < n; i ++)pre[i] = Math.max(height[i],pre[i - 1]);
for(int i = n - 2; i >= 0; i --)suf[i] = Math.max(height[i],suf[i + 1]);
int rainCount = 0;
for(int i = 0; i < n; i ++)rainCount += Math.min(pre[i],suf[i]) - height[i];
return rainCount;
}
}