企业如何应用网站的,怎么做平台网站,建设网站如何选择服务器,个人网站建设心得接雨水 1、 题目描述2、解题思路 1、 题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。
2、解题思路
本题使用了双指针#xff0c;根据下图可以得出#xff0c;下标 i 处能接的雨水量由左边… 接雨水 1、 题目描述2、解题思路 1、 题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。
2、解题思路
本题使用了双指针根据下图可以得出下标 i 处能接的雨水量由左边最大值 leftMax 和右边最大值 rightMax 中的最小值决定因此设置左指针left和右指针right左指针只会向右移动右指针只会向左移动遍历的过程中持续更新 leftMax 和 rightMax 。
若 leftMax rightMax下标 left 处能接的雨水量等于 leftMax−height[left]将下标 left 处能接的雨水量加到能接的雨水总量然后将 left 加 1即向右移动一位若 leftMax ≥ rightMax下标 right 处能接的雨水量等于 rightMax−height[right]将下标 right 处能接的雨水量加到能接的雨水总量然后将 right 减 1即向左移动一位 class Solution {public int trap(int[] height) {// 定义左右指针int left0,rightheight.length-1;// 定义左边最大值和右边最大值int leftMax0,rightMax0;// 定义最终结果int ans 0;// 两个指针相遇为循环结束条件while(leftright){// 判断当前高度是否比最大高度大若是更新最大高度if(height[left]leftMax)leftMax height[left];if(height[right]rightMax)rightMax height[right];// 下标i处能接到的雨水量由leftMax和rightMax的最小值决定if(leftMaxrightMax){ans leftMax-height[left];left;}else{ans rightMax-height[right];right--;}}return ans;}
}时间复杂度O(n)其中 n 是数组 height 的长度。两个指针的移动总次数不超过 n。空间复杂度O(1)。只需要使用常数的额外空间。
