顺德销售型网站建设,网页设计实训报告大专,苏州新区建网站,最好的医疗网站建设目录
1、题目介绍
2、解题思路
2.1、暴力破解法
2.2、双指针法 1、题目介绍
原题链接#xff1a; 42. 接雨水 - 力扣#xff08;LeetCode#xff09; 示例 1#xff1a; 输入#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1]输出#xff1a;6解释#xff1a;上面是由…目录
1、题目介绍
2、解题思路
2.1、暴力破解法
2.2、双指针法 1、题目介绍
原题链接 42. 接雨水 - 力扣LeetCode 示例 1 输入height [0,1,0,2,1,0,1,3,2,1,2,1]输出6解释上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图在这种情况下可以接 6 个单位的雨水蓝色部分表示雨水。 示例 2 输入height [4,2,0,3,2,5]输出9 提示 n height.length1 n 2 * 1040 height[ i ] 105 2、解题思路 2.1、暴力破解法 首先看到这题的第一反应就是通过每层遍历去找出蓝色块即水块。 只要找到每一层的边界再通过右边界right - 左边界left 1即可得出该层蓝色块与黑色块的总和再通过遍历去掉黑色块就能够得出单层的水块最终将每一层水块累加则得出结果。 图解说明 第一层 通过计算找出第一层的边界可以发现第一层的边界规律是只要左边界left从左往右找到第一个大于等于1的柱子即是左边界而右边界right从右往左找到第一个大于等于1的柱子即为右边界。再通过right - left 1即11-11 11得到第一层所有所有区域总和len然后从left进行遍历数组到right 只要当前值大于等于1则len自减1。最后减完之后得出的len即为第一层水块数。 第二层 同理只要左边界left从左往右找到第一个大于等于2的柱子即是左边界而右边界right从右往左找到第一个大于等于2的柱子即为右边界。再通过right - left 1即8得到第二层所有所有区域总和len然后从left进行遍历数组到right 只要当前值大于等于2则len自减1。最后减完之后得出的len即为第二层水块数。 第三层 当边界left right 时循环结束此时第三层的left等于right直接退出循环不需要计算。 代码实现 其中 heightMax方法用于计算整个数组的最大值也就是最大层数最大层数有多少就需要遍历多少次。 layerNumber方法用于计算每一层的水块个数。 class Solution {public int trap(int[] height) {int left 0;int right height.length - 1;int sum 0;int max heightMax(height); //计算出最大层数for(int i 1; i max; i) { //几层就循环几次if(left right) {while(height[left] i) { //找出左边界left;}while(height[right] i) { //找出右边界right--;}int ret layerNumber(height,left,right,i); //计算该层的水块sum ret; //sum记录水块个数}}return sum;}public int heightMax(int[] arr) {int max arr[0];for(int i 1; i arr.length; i) {max max arr[i] ? max : arr[i];}return max;}signal是当前所在层数public int layerNumber(int[] arr, int left, int right, int signal) { int len right - left 1; //画图理解1for(int i left; i right; i) {if(arr[i] signal) {len--;}}return len;}
} 但是由于是暴力破解每层都需要依次遍历因此时间复杂度和空间复杂度非常高。 下面给大家讲解一个巧妙运用双指针在动态规划下快速计算出结果的算法。
2.2、双指针法 leftMax用于记录当前左指针left经过的最大高度同理rightMax用于记录当前左指针right经过的最大高度。 下标 i 处能否接水以及接到水的数量其实取决于左指针left到 i 时所经过的最大高度leftMax与右指针right到 i 时所经过的最大高度rightMax它们之间的较小值。 例如 下标5处它能接到水的数量是leftMax和rightMax的最小值减去下标 i 的高度。 再例如 下标9处它能接到水的数量是leftMax和rightMax的最小值减去下标 i 的高度。 代码实现
class Solution {public int trap(int[] height) {int left 0;int right height.length - 1;int leftMax 0;int rightMax 0;int sum 0;while(left right) {leftMax Math.max(leftMax,height[left]); //每次循环前判断最大值rightMax Math.max(rightMax,height[right]); //每次循环前判断最大值//谁小移动谁并且移动前计算当前位置与最大高度的差值,差值即水量数。if(leftMax rightMax) { sum rightMax - height[right];right--;}else{ //相等时移动哪一个都可以这里移动leftsum leftMax - height[left];left;}}return sum;}
}
复杂度分析 时间复杂度O(n)其中 n 是数组 height 的长度。两个指针的移动总次数不超过 n。 空间复杂度O(1)。只需要使用常数的额外空间。 使用该方法能够大大降低时间复杂度。 更多【LeetCode刷题】推荐
【LeetCode力扣】189 53 轮转数组 | 最大子数组和-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/134095703?spm1001.2014.3001.5502
【LeetCode力扣】234 快慢指针 | 反转链表 | 还原链表-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/133958602?spm1001.2014.3001.5502
【LeetCode力扣】86. 分隔链表-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/133942678?spm1001.2014.3001.5502 如果觉得作者写的不错求给博主一个大大的点赞支持一下你们的支持是我更新的最大动力
如果觉得作者写的不错求给博主一个大大的点赞支持一下你们的支持是我更新的最大动力
如果觉得作者写的不错求给博主一个大大的点赞支持一下你们的支持是我更新的最大动力
