var trap = function(height) { let sum = 0; for (let i = 1; i < height.length; i++) { let leftMax = 0; for (let j = i - 1; j >= 0; j--) { if (height[j] > leftMax) leftMax = height[j]; } let rightMax = 0; for (let j = i + 1; j <= height.length; j++) { if (height[j] > rightMax) rightMax = height[j]; } let data = Math.min(leftMax, rightMax) - height[i]; sum += data > 0 ? data : 0; } return sum;};
解法二
空间换时间处理下
时间复杂度 O(n) 2 个独立的循环 2n
空间复杂度 O(n) 创建 2 个长度为 n 的空间
var trap = function(height) { let sum = 0; let leftMax = 0; let rightMax = [0]; for (let i = height.length - 1; i > 0; i--) { rightMax[i] = Math.max(rightMax[i + 1] || 0, height[i]); } for (let i = 1; i < height.length; i++) { leftMax = Math.max(leftMax, height[i]); let data = Math.min(leftMax, rightMax[i]) - height[i]; sum += data > 0 ? data : 0; } return sum;};
解法三
使用双指针优化下空间
时间复杂度 O(n) left 和 right 正好走完一个循环
空间复杂度 O(1) 创建 5 个常量空间
var trap = function(height) { let sum = 0; let leftMax = 0; let rightMax = 0; let left = 0; let right = height.length - 1; while (left < right) { if (height[left] < height[right]) { if (height[left] >= leftMax) { leftMax = height[left]; } else { sum += leftMax - height[left]; } left++; } else { if (height[right] >= rightMax) { rightMax = height[right]; } else { sum += rightMax - height[right]; } right--; } } return sum;};
看懂题解才写出来 太难了
参考回答
前置知识
空间换时间
双指针
单调栈
双数组
思路
这是一道雨水收集的问题， 难度为hard. 如图所示，让我们求下过雨之后最多可以积攒多少的水。
如果采用暴力求解的话，思路应该是 height 数组依次求和，然后相加。
伪代码:
for (let i = 0; i < height.length; i++) { area += (h[i] - height[i]) * 1; // h为下雨之后的水位}
问题的关键在于求解左边柱子最大值和右边柱子最大值,
我们其实可以用两个数组来表示leftMax, rightMax，
以 leftMax 为例，leftMax[i]代表 i 的左侧柱子的最大值，因此我们维护两个数组即可。
关键点解析
建模 h[i] = Math.min(左边柱子最大值, 右边柱子最大值)(h 为下雨之后的水位)
代码
代码支持 JavaScript，Python3，C++:
JavaScript Code:
/* * @lc app=leetcode id=42 lang=javascript * * [42] Trapping Rain Water * *//** * @param {number[]} height * @return {number} */var trap = function(height) { let max = 0; let volumn = 0; const leftMax = []; const rightMax = []; for (let i = 0; i < height.length; i++) { leftMax[i] = max = Math.max(height[i], max); } max = 0; for (let i = height.length - 1; i >= 0; i--) { rightMax[i] = max = Math.max(height[i], max); } for (let i = 0; i < height.length; i++) { volumn = volumn + Math.min(leftMax[i], rightMax[i]) - height[i]; } return volumn;};
Python Code:
class Solution: def trap(self, heights: List[int]) -> int: n = len(heights) l, r = [0] * (n + 1), [0] * (n + 1) ans = 0 for i in range(1, len(heights) + 1): l[i] = max(l[i - 1], heights[i - 1]) for i in range(len(heights) - 1, 0, -1): r[i] = max(r[i + 1], heights[i]) for i in range(len(heights)): ans += max(0, min(l[i + 1], r[i]) - heights[i]) return ans
C++ Code:
int trap(vector<int>& heights){ if(heights == null) return 0; int ans = 0; int size = heights.size(); vector<int> left_max(size), right_max(size); left_max[0] = heights[0]; for (int i = 1; i < size; i++) { left_max[i] = max(heights[i], left_max[i - 1]); } right_max[size - 1] = heights[size - 1]; for (int i = size - 2; i >= 0; i--) { right_max[i] = max(heights[i], right_max[i + 1]); } for (int i = 1; i < size - 1; i++) { ans += min(left_max[i], right_max[i]) - heights[i]; } return ans;}
class Solution: def trap(self, heights: List[int]) -> int: n = len(heights) l_max = r_max = 0 l, r = 0, n - 1 ans = 0 while l < r: if heights[l] < heights[r]: if heights[l] < l_max: ans += l_max - heights[l] else: l_max = heights[l] l += 1 else: if heights[r] < r_max: ans += r_max - heights[r] else: r_max = heights[r] r -= 1 return ans
class Solution {public: int trap(vector<int>& heights){ int left = 0, right = heights.size() - 1; int ans = 0; int left_max = 0, right_max = 0; while (left < right) { if (heights[left] < heights[right]) { heights[left] >= left_max ? (left_max = heights[left]) : ans += (left_max - heights[left]); ++left; } else { heights[right] >= right_max ? (right_max = heights[right]) : ans += (right_max - heights[right]); --right; } } return ans;}};
