当前位置: 首页 > news >正文

接雨水

接雨水

  • 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 left=0,right=height.length-1;// 定义左边最大值和右边最大值int leftMax=0,rightMax=0;// 定义最终结果int ans = 0;// 两个指针相遇为循环结束条件while(left<right){// 判断当前高度是否比最大高度大,若是,更新最大高度if(height[left]>leftMax)leftMax = height[left];if(height[right]>rightMax)rightMax = height[right];// 下标i处能接到的雨水量由leftMax和rightMax的最小值决定if(leftMax<rightMax){ans += leftMax-height[left];left++;}else{ans += rightMax-height[right];right--;}}return ans;}
}
  • 时间复杂度:O(n),其中 n 是数组 height 的长度。两个指针的移动总次数不超过 n。
  • 空间复杂度:O(1)。只需要使用常数的额外空间。
http://www.lryc.cn/news/488817.html

相关文章:

  • Python蓝桥杯刷题1
  • 实习冲刺第二十七天
  • el-table-column自动生成序号在序号前插入图标
  • 前端工程化-node/npm/babel/polyfill/webpack 一文速通
  • Spring Security PasswordEncoder接口(密码编码)
  • C# 数据结构之【树】C#树
  • 树莓派2装FreeBSD14.1 Raspberry Pi2 install FreeBSD14.1 00000121:error:0A000086:SSL
  • 探索C/C++的奥秘之stack和queue
  • [开源]1.2K star!中后台方向的低代码可视化平台,超赞!
  • 算法编程题-排序
  • 【AIGC】如何准确引导ChatGPT,实现精细化GPTs指令生成
  • 【Axure高保真原型】或和且条件
  • KubeVirt下gpu operator实践(GPU直通)
  • Vue通过file控件上传文件到Node服务器
  • 如何在 SQL Server 中新增账户并指定数据库权限
  • c#编码技巧(十九):各种集合特点汇总
  • 汽车软件DevOps解决方案
  • 同步的意义以及机制
  • leetcode 面试150之 156.LUR 缓存
  • 启发式搜索算法复现
  • 【IDE】使用指南
  • 设计编程网站集:简述可扩展性系统设计(笔记)
  • 「Mac玩转仓颉内测版25」基础篇5 - 布尔类型详解
  • Fashion-VDM:引领视频虚拟试穿技术的新篇章
  • Scala中的集合复习(1)
  • Java依赖包漏洞检测命令
  • 【Java】强制类型转换
  • RabbitMQ消息可靠性保证机制4--消费端限流
  • 查找萤石云IOS Sdk中的编解码接口
  • erchas