便宜点的网站空间,c2c代表平台有哪些,鹿岛建设 网站,专门做二手的网站【前后缀】【双指针】Leetcode 42. 接雨水 解法1 前后缀分解解法2 双指针 ---------------#x1f388;#x1f388;42. 接雨水 题目链接#x1f388;#x1f388;-------------------
解法1 前后缀分解 维护一个前缀#xff08;左侧最高#xff09;后缀#xff08;右侧… 【前后缀】【双指针】Leetcode 42. 接雨水 解法1 前后缀分解解法2 双指针 ---------------42. 接雨水 题目链接-------------------
解法1 前后缀分解 维护一个前缀左侧最高后缀右侧最高数组 把每一个小区间看做一个桶桶的容量取决于左右壁中最低的那一个Minleftmaxrightmax 左壁就是当前这块及其左侧高度的最大值前缀 leftmax 右壁就是当前这块及其右侧高度的最大值后缀 rightmax 最终能装的水 当前小桶的容量-当前小柱子高度 时间复杂度O(N) 空间复杂度O(N)
class Solution {public int trap(int[] height) {// 把每一个小区间看做一个桶桶的容量取决于左右壁中最低的那一个Minleftmaxrightmax// 左壁就是当前这块及其左侧高度的最大值前缀 leftmax// 右壁就是当前这块及其右侧高度的最大值后缀 rightmax// 能装的水 桶容量-柱子高度int[] leftmax new int[height.length]; // 左边的最大高度int[] rightmax new int[height.length]; // 右边的最大高度int templeftmax 0;for(int i 0; i height.length;i){ // 前缀数组if(height[i] templeftmax){templeftmax height[i];}leftmax[i] templeftmax;}int temprightmax 0;for(int i height.length-1; i 0;i--){ // 后缀数组if(height[i] temprightmax){temprightmax height[i];}rightmax[i] temprightmax;}int totalWater 0;// 同时遍历前后缀数组两者取取Min即为桶内可以容纳的高度。之后减去筒高度即为水的高度累加即可for(int i 0; i height.length; i){totalWater Math.min(leftmax[i],rightmax[i])-height[i];}return totalWater;}
} 解法2 双指针 多做做吧 不行就看看动图 双指针法 whileleftright 每次更新前缀最大值和后缀最大值 ⭐️当 前缀最大值 后缀最大值时当前的桶容量肯定为前缀最大值 ⭐️当 后缀最大值 前缀最大值时当前的桶容量肯定为后缀最大值 之后就更新totalwater 当前桶容量- 底部高度即可 时间复杂度O(N) 空间复杂度O(1)⭐️⭐️
class Solution {public int trap(int[] height) {int totalWater 0;// 初始化双指针 一个指头一个指尾int left 0;int right height.length-1;// 前缀最大值和后缀最大值int preMax 0;int backMax 0;// 双指针left right遍历while(left right){// 更新前缀最大值和后缀最大值preMax Math.max(preMax, height[left]);backMax Math.max(backMax, height[right]);// 1.当前缀最大值 小于 后缀最大值说明桶容量一定为前缀最大值if(preMax backMax){totalWater (preMax-height[left]); // 计算totalwater 桶容量-柱子高度left;}// 2.当后缀最大值 小于 前缀最大值说明桶容量一定为后缀最大值if(preMax backMax){totalWater (backMax-height[right]); // 计算totalwater 桶容量-柱子高度right--;}// 3.前缀最大值和后缀最大值相等的时候随便归入一类就行}return totalWater;}
}
