LeetCode Hot 100:42. 接雨水

題目

給定?n 個非負整數表示每個寬度為 1 的柱子的高度圖,計算按此排列的柱子,下雨之后能接多少雨水。

解析

和題目 盛水最多的容器 類似,

LeetCode Hot 100:11. 盛最多水的容器-CSDN博客

只是這里將每一個柱子視為一個寬度為1的容器,能接水的體積取決于左邊最大高度和右邊最大高度的較小值,再減去底部當前柱子的高度。設置左右指針left和right,指向左右兩側當前待計算接水量的柱子,以及記錄左指針以左、右指針以右的最大高度值的pre_max和suf_max兩個變量。

作者:靈茶山艾府

來源:

盛最多水的容器 接雨水【基礎算法精講 02】_嗶哩嗶哩_bilibili

答案

注意while循環可以不加等號,因為在「誰小移動誰」的規則下,相遇的位置一定是最高的柱子,這個柱子是無法接水的。

作者:靈茶山艾府

來源:42. 接雨水 - 力扣(LeetCode)

/*** @param {number[]} height* @return {number}*/
var trap = function(height) {const len = height.length;let left = 0, right = len - 1, ans = 0;    //設置左右指針和初始答案//初始化前綴最大高度(左指針以左),后綴最大高度(右指針以右)let pre_max = 0, suf_max = 0;while(left < right) {pre_max = Math.max(pre_max, height[left]);    //更新前綴最大高度suf_max = Math.max(suf_max, height[right]);    //更新后綴最大高度    if(pre_max < suf_max) {    //判斷儲水高度,取決于前綴、后綴最大高度中的短邊ans += pre_max - height[left];    //實際可儲水高度需要減去底部柱子的高度left++;} else {ans += suf_max - height[right];right--;}}return ans;
};

復雜度分析

時間復雜度:O(n),其中?n?為?height?的長度。

空間復雜度:O(1),僅用到若干額外變量。

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/web/91504.shtml
繁體地址,請注明出處:http://hk.pswp.cn/web/91504.shtml
英文地址,請注明出處:http://en.pswp.cn/web/91504.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

【C語言入門級教學】字符指針變量

文章目錄1.字符指針變量2. 數組指針變量2.1 數組指針變量初始化3.?維數組傳參的本質1.字符指針變量 在指針的類型中我們知道有?種指針類型為字符指針 char* ; ?般使?: int main() { char ch w; char* pc &ch;//pc的類型是char**pcw;//對pc解引用 修改ch存放的內容…

【Shell腳本自動化編寫——報警郵件,檢查磁盤,web服務檢測】

Shell腳本自動化編寫Shell腳本自動化編寫一、判斷當前磁盤剩余空間是否有20G&#xff0c;如果小于20G&#xff0c;則將報警郵件發送給管理員&#xff0c;每天檢查一次磁盤剩余空間。第一步&#xff1a;準備工作第二步&#xff1a;配置郵件信息第三步&#xff1a;檢查磁盤的自動…

Java 接口(下)

三、接口的繼承性【基礎重點】 1. Java中的接口之間的繼承關系是多繼承&#xff0c;一個接口可以有多個父接口(1) 語法&#xff1a;interface 接口名 extends 父接口1,父接口2{} 2. 類和接口之間是多實現的關系&#xff1a;一個類可以同時實現多個接口(1) 語法&#xff1a;clas…

學習游戲制作記錄(各種水晶能力以及多晶體)8.1

1.實現創建水晶并且能與水晶進行交換位置的能力創建好水晶的預制體&#xff0c;添加動畫控制器&#xff0c;傳入待機和爆炸的動畫創建Crystal_Skill_Control腳本&#xff1a;掛載在水晶預制體上private float crystalExstTime;//水晶存在時間public void SetupCrystal(float _c…

在vscode 如何運行a.nut 程序(Squirrel語言)

在 VS Code 中運行 Squirrel 語言編寫的 .nut 程序&#xff0c;需要先配置 Squirrel 運行環境并安裝相關插件&#xff0c;具體步驟如下&#xff1a; 一、安裝 Squirrel 解釋器 Squirrel 程序需要通過其官方解釋器 squirrel 或 sq 執行&#xff0c;首先需要安裝解釋器&#xf…

【數據結構】生活中的數據結構:從吃飯與編程看棧與隊列思維

生活中的數據結構&#xff1a;從吃飯與編程看棧與隊列思維 在軟件開發的世界里&#xff0c;棧&#xff08;Stack&#xff09;和隊列&#xff08;Queue&#xff09;是兩種基礎的數據結構&#xff0c;它們以不同的順序管理數據&#xff1a;棧遵循后進先出&#xff08;LIFO&#x…

牛客——接頭密匙

題目鏈接&#xff1a;牛客--接頭密匙 該題是一個很顯然的前綴樹問題&#xff0c;只需要構建a中所有數組對應的前綴樹&#xff0c;之后求b所處前綴個數即可。關于前綴樹的構建&#xff0c;可以觀看左老師算法講解045的視頻&#xff0c;簡單來講就是用特殊字符將實際數據隔開&…

【Linux基礎知識系列】第六十三篇 - 文件編輯器基礎:vim

在 Linux 系統中&#xff0c;文本編輯器是系統管理員和開發人員不可或缺的工具。vim 是一個功能強大的文本編輯器&#xff0c;廣泛應用于 Linux 系統中。它支持多種編輯模式&#xff0c;提供了豐富的文本編輯功能&#xff0c;適用于編寫代碼、配置文件和文檔。掌握 vim 的基本使…

音頻驅動的視覺特效:粒子、動畫與Shader的融合技術

音頻驅動視覺效果的實現與應用1. 引言在互動媒體、游戲和數字藝術領域&#xff0c;音頻數據實時控制視覺元素已成為核心技術&#xff0c;它能創造沉浸式體驗&#xff0c;增強用戶參與感。例如&#xff0c;音樂會可視化或VR游戲中&#xff0c;音頻信號驅動粒子流動、動畫變化和S…

機器學習環境配置

【終極指南】吃透機器學習環境配置&#xff1a;從Conda、CUDA到Docker容器化 大家好&#xff01;在機器學習的旅程中&#xff0c;一個穩定、可復現的環境是成功的基石。 第一部分&#xff1a;核心理念——為何環境配置如此重要&#xff1f; 任何機器學習模型的運行&#xff0c;…

【14】大恒相機SDK C#開發 ——Bitmap.UnlockBits()什么意思?有什么用?bmpData.Scan0;什么意思?有什么用?

文章目錄1 Bitmap.UnlockBits()2 bmpData.Scan01 Bitmap.UnlockBits() 在 C# 中&#xff0c;Bitmap.UnlockBits() 方法的作用是解鎖通過 Bitmap.LockBits() 方法鎖定的位圖數據&#xff0c;并釋放相關的位圖數據結構。 當你使用 Bitmap.LockBits() 方法鎖定位圖數據時&#x…

什么是doris

文章目錄簡介使用場景Apache Doris 主要應用于以下場景&#xff1a;實時數據分析&#xff1a;湖倉融合分析&#xff1a;半結構化數據分析&#xff1a;Apache Doris 的核心特性詳細請看官方文檔&#xff1a; Apache Doris介紹簡介 Apache Doris 是一款基于 MPP 架構的高性能、實…

python+pyside6的簡易畫板

十分簡單的一個畫板程序&#xff0c;用QLabel控件作為畫布&#xff0c;在畫布上可以畫出直線、矩形、填充矩形、園&#xff0c;橢園、隨手畫、文本等內容。將原先發布的畫板程序中的畫文本方法修改成了原位創建一編輯框&#xff0c;編輯框失去焦點后&#xff0c;即將文本畫在畫…

【數據可視化-76】從釋永信被查,探索少林寺客流量深度分析:Python + Pyecharts 炫酷大屏可視化(含完整數據和代碼)

&#x1f9d1; 博主簡介&#xff1a;曾任某智慧城市類企業算法總監&#xff0c;目前在美國市場的物流公司從事高級算法工程師一職&#xff0c;深耕人工智能領域&#xff0c;精通python數據挖掘、可視化、機器學習等&#xff0c;發表過AI相關的專利并多次在AI類比賽中獲獎。CSDN…

WPF TreeView自帶自定義滾動條

放在TreeView.Resources中&#xff1a;<Style TargetType"ScrollBar"><Setter Property"Stylus.IsPressAndHoldEnabled" Value"false"/><Setter Property"Stylus.IsFlicksEnabled" Value"false"/><Set…

MongoDB 詳細用法與 Java 集成完整指南

MongoDB 詳細用法與 Java 集成完整指南 目錄 MongoDB 基礎概念MongoDB 安裝與配置MongoDB Shell 基本操作Java 環境準備Java MongoDB 驅動集成連接配置基本 CRUD 操作高級查詢操作索引操作聚合管道事務處理Spring Boot 集成最佳實踐 1. MongoDB 基礎概念 1.1 核心概念對比 …

【Flutter3.8x】flutter從入門到實戰基礎教程(四):自定義實現一個自增的StatefulWidget組件

fluttet中實現一個自定義的StatefulWidget組件&#xff0c;可以在數據變化后&#xff0c;把最新的頁面效果展示給客戶 實現效果實現代碼 pages文件夾下新加一個counter_page.dart文件 class CounterPage extends StatefulWidget {const CounterPage({super.key});overrideState…

[AI8051U入門第十三步]W5500實現MQTT通信

前言 學習目標: 1、學習MQTT協議 2、了解MQTT數據幀格式 3、自己編寫MQTT程序 4、調試MQTT程序一、MQTT協議介紹 MQTT(Message Queuing Telemetry Transport) 是一種輕量級的 發布/訂閱(Pub/Sub) 消息傳輸協議,專為 低帶寬、高延遲或不可靠網絡 環境設計,廣泛應用于 物…

四、基于SpringBoot,MVC后端開發筆記

整合第三方技術&#xff1a; 1、整合Junit (1)名稱&#xff1a;SpringBootTest (2)類型&#xff1b;測試類注解 (3)位置&#xff1a;測試類定義上方 (4)作用&#xff1a;設置Junit加載的SpringBoot啟動類 (5)相關屬性&#xff1a;classes&#xff1a;設置SpringBoot啟動類 2、整…

深入講講異步FIFO

一、異步 FIFO 的基本概念1.1 定義與核心作用異步 FIFO&#xff08;Asynchronous FIFO&#xff09;是一種讀寫時鐘完全獨立的先進先出&#xff08;First-In-First-Out&#xff09;數據緩沖器&#xff0c;主要用于跨時鐘域數據傳輸場景。在數字系統中&#xff0c;當兩個模塊工作…