一、题目
二、解题思路
class Solution {
/**
* 优化:提前先把每个格子对应的左边、右边最大值算出来,这样就可以将时间复杂度降到O(n)
*
*/
public int trap(int[] height) {
if (height == null || height.length <= 0) {
return 0;
}
int res = 0;
int[] maxLeftArrs = new int[height.length];
maxLeftArrs[0] = height[0];
for (int i = 1; i < height.length; i++) {
maxLeftArrs[i] = Math.max(height[i], maxLeftArrs[i - 1]);
}
int[] maxRightArrs = new int[height.length];
maxRightArrs[height.length - 1] = height[height.length - 1];
for (int i = height.length - 2; i > 0; i--) {
maxRightArrs[i] = Math.max(height[i], maxRightArrs[i + 1]);
}
for (int i = 1; i < height.length - 1; i++) {
res += Math.min(maxLeftArrs[i], maxRightArrs[i]) - height[i];
}
return res;
}
/**
* 有点难理解,需要看图才知道
*
* 思路:暴力解法
* (1)当前格子内,先找出左边最高的高度,再找出右边最高的高度
* (2)左边和右边最小值减去当前高度,即为当前格子能盛水的最大值
* 时间复杂度:O(n2)
* 空间复杂度:O(1)
*
*/
public int trap2(int[] height) {
int res = 0;
for (int i = 1; i < height.length - 1; i++) {
int maxLeft = 0;
int maxRight = 0;
for (int j = i; j >= 0; j--) {
maxLeft = Math.max(maxLeft, height[j]);
}
for (int j = i; j < height.length; j++) {
maxRight = Math.max(maxRight, height[j]);
}
res += Math.min(maxLeft, maxRight) - height[i];
}
return res;
}
}