做设计去那些网站找素材,山东seo网站推广,软件最全的软件商店,仿小刀娱乐wordpress主题Problem: 42. 接雨水 文章目录 思路解题方法复杂度Code 思路 要能接住雨水#xff0c;感性的认知就是要形成一个“下凹区域”#xff0c;则此时我们就要比较当前柱子和其左右柱子高度的关系#xff0c;易得一个关键的式子#xff1a;当前小区域的积水 min#xff08;当前… Problem: 42. 接雨水 文章目录 思路解题方法复杂度Code 思路 要能接住雨水感性的认知就是要形成一个“下凹区域”则此时我们就要比较当前柱子和其左右柱子高度的关系易得一个关键的式子当前小区域的积水 min当前柱子左侧最高柱子高度当前柱子右侧最高柱子高度 - 当前柱子高度但我们也应当注意按上式得出的结果当前小区域的积水可能为负值因为当前柱子的高度可能大于min当前柱子左侧最高柱子高度当前柱子右侧最高柱子高度实际情况也就是无法形成一个接住水的区域则我们将其设置为0。 解题方法 1.暴力法一遍遍历每次寻找当前柱子左、右侧的最高柱子再将min当前柱子左侧最高柱子高度当前柱子右侧最高柱子高度 - 当前柱子高度加到结果上注意若其结果为正则直接加为负置为0 2.前缀和先通过遍历每次记录当前柱子及其左侧的最高值和当前柱子及其右侧柱子的最高值再将min当前柱子及其左侧的最高值当前柱子及其右侧柱子的最高值-当前柱子的高度值加到结果上注意此时由于在记录当前柱子及其左侧的最高值和当前柱子及其右侧柱子的最高值的操作中已经记录了当前柱子的高度值则最后再不用判断每次要加到结果上的值是否小于0 复杂度
时间复杂度: 暴力法 O ( n 2 ) O(n^2) O(n2) 前缀和 O ( n ) O(n) O(n) 空间复杂度: 暴力法 O ( 1 ) O(1) O(1) 前缀和 O ( n ) O(n) O(n) Code
class Solution {//暴力法//Time Complexity: O(N^2)//Space Complexity: O()public int trap(int[] height) {int res 0;//从第2个柱子开始到倒数第二个for (int i 1; i height.length - 1; i) {//寻找当前左侧最高柱子int leftMax 0;for (int j 0; j i; j) {if (height[j] leftMax) {leftMax height[j];}}//寻找当前右侧最高柱子int rightMax 0;for (int j i 1; j height.length; j) {if (height[j] rightMax) {rightMax height[j];}}//当前柱子两侧最高柱子的较低值//减去当前柱子的长度即为当前储水量//如果carry小于0则为0int carry Math.min(rightMax,leftMax) - height[i];if (carry 0) carry 0;res carry;}return res;}
}class Solution {//前缀数组//Time Complexity: O(N)//Space Complexity: O(N)public int trap(int[] height) {int n height.length;//前缀maxint[] leftMax new int[n];int max 0;for (int i 0; i n; i) {//寻找当前左边包括本身的最大值leftMax[i] Math.max(max,height[i]);max leftMax[i];}//后缀maxint[] rightMax new int[n];max 0;for (int i n - 1; i 0; --i) {//寻找当前右边边包括本身的最大值rightMax[i] Math.max(max,height[i]);max rightMax[i];}//计算柱子之上接到的雨水int res 0;for (int i 1; i n - 1; i) {res Math.min(leftMax[i], rightMax[i]) - height[i];}return res;}
}
