前言
给你输入一个长度为 n 的 nums 数字代表二维平面内一排宽度为 1 的柱子，每个元素 nums[i] 都是非负整数，代表第 i 个柱子的告诉。现在请你计算，如果下雨了，这些柱子能够装下多少雨水？
接雨水
正文
直接上思路吧
//@ts-ignore ;(() => { function trap(input: number[]): number { ...... } let input = [4, 5, 2, 5, 3, 5, 4, 10, 434, 3, 434, 42, 34, 34] // 1. let result = trap(input) // 2. console.log("result -> ", result) })()
- input 是输入数组
- trap 是待实现的函数
函数实现
function trap(input: number[]): number { if (input.length === 0) return 0 let n = input.length // 1. let left = 0; // 2. let right = n - 1; // 3. // result let ans = 0; // 4. let l_max = input[0], r_max = input[n - 1] // 5. while (left <= right) { // 6. l_max = Math.max(l_max, input[left]) r_max = Math.max(r_max, input[right]) if (l_max < r_max) { ans += l_max - input[left] // 7. left++ } else { ans += r_max - input[right] // 8. right-- } } return ans }
- 数组长度
- 初始最左边元素数组下标
- 初始化最右边元素数组下标
- 返回结果
- l_max:数组左边的最大值、r_max:数组右边的最大值
- 可以看到这里的双指针和快速排序里类似
- 当左边最大元素小于右边最大元素时，此时的左边元素的积水量取决于左边最大元素
- 当左边最大元素小于等于右边最大元素时，此时的右边元素的积水量取决于右边最大元素
完整测试案例
//@ts-ignore ;(() => { function trap(input: number[]): number { if (input.length === 0) return 0 let n = input.length let left = 0; let right = n - 1; // result let ans = 0; let l_max = input[0], r_max = input[n - 1] while (left <= right) { l_max = Math.max(l_max, input[left]) r_max = Math.max(r_max, input[right]) if (l_max < r_max) { ans += l_max - input[left] left++ } else { ans += r_max - input[right] right-- } } return ans } let input = [4, 5, 2, 5, 3, 5, 4, 10, 434, 3, 434, 42, 34, 34] let result = trap(input) console.log("result -> ", result) })()
执行结果
执行结果
总结
就像处理字符串问题，不要考虑如何处理整个字符串，而是思考应该如何处理每一个字符。我们不要想整体，而应该想局部。
不过矛盾的是：什么时候想整体？什么时候切换到想局部？目前靠的经验，要达到没有就具体问题切换自如的境界还需要勤加练习！非要说诀窍的话，那就是把“整体”、“局部”先刻在脑子里，跟解决动态规划问题一样，作为备忘录，每每遇到先检查一遍比较好。
