积雨问题
题目:求下雨后一个砖型序列能积多少单位的雨
例子:
// 砖型序列
const blocks = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
// 结果:6
分析:木桶原理,针对其中某个节点,其左侧的最高节点和其右侧最高节点(两个节点都高于当前节点),组成的当前节点木桶
当前节点可以积雨量 = 木桶的最短值 - 当前节点高度
思路一: 根据上述分析得到公式
itemRainCount = min(leftMax, rightMax) - item
上代码
const calculateRain = function(array: number[]) {
let sum = 0;
for (let i = 1; i < array.length - 1; i++) {
let itemLeftMax = array[0];
for (let leftI = 1; leftI < i; leftI++) {
itemLeftMax = Math.max(array[leftI], itemLeftMax);
}
let itemRightMax = array[i + 1];
for (let rightI = i + 1; rightI < array.length; rightI++) {
itemRightMax = Math.max(array[rightI], itemRightMax);
}
const itemRain = Math.min(itemLeftMax, itemRightMax) - array[i];
sum += itemRain > 0 ? itemRain : 0; // 当前节点高与左侧右侧节点
}
return sum;
};
思路二:上述思路的时间复杂度为 O(n^2),使用动态规划的方式从当前节点计算左右的增量,增量有效则将其存储下来,将左侧增量与右侧增量对比,去木桶最小值然后剪去当前节点高度就是当前节点的积雨量,照旧,leetcode 上面的图画的很好
上代码
const array = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
const rain = function(array: number[]) {
let rainSum = 0;
const leftMax = [array[0]];
const rightMax = [];
rightMax[array.length - 1] = array[array.length - 1];
for (let i = 1; i < array.length; i++) {
leftMax[i] = Math.max(leftMax[i - 1], array[i]);
}
for (let i = array.length - 2; i >= 0; i--) {
rightMax[i] = Math.max(rightMax[i + 1], array[i]);
}
for (let i = 0; i < array.length; i++) {
rainSum += Math.min(leftMax[i], rightMax[i]) - array[i];
}
return rainSum;
};
思路三:上述方法时间复杂度减少到了 O(n), 但是却开辟了两个数组存储增量数据的节点,增加了空间复杂度,下面介绍一种方式来减少空间复杂度 双指针。使用两个指针标记组数两头的节点,对比指针节点的木桶值,向内取遍历节点,取到向左向右移动的增量最大值,然后获取每个节点的积雨量,获取 sum 值。
先上代码:
const array = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
const rain3 = function(array: number[]) {
let leftMax = 0;
let rightMax = 0;
let left = 1;
let right = array.length - 2;
let sum = 0;
for (let i = 1; i < array.length - 1; i++) {
if (array[left - 1] < array[right + 1]) {
leftMax = Math.max(leftMax, array[left - 1]);
if (leftMax > array[left]) {
sum += leftMax - array[left];
}
left++;
} else {
rightMax = Math.max(rightMax, array[right + 1]);
if (rightMax > array[right]) {
sum += rightMax - array[right];
}
right--;
}
}
return sum;
};