【LeetCode】接雨水

目錄

  • 一、題目
  • 二、解法
  • 完整代碼


一、題目

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

示例 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.length
1 <= n <= 2 * 104
0 <= height[i] <= 105


二、解法

可以把水分隔開,相當于m個水柱,把所有的水柱加在一起就好了。
在這里插入圖片描述
圖看懂了,接下來就很簡單了,left數組和right數組,分別記錄每個點的左邊的最高值,和右邊的最高值
當我們到i的時候,i左邊的最高值left[i]就是i-1時遇到的最高值以及i的柱子高度


完整代碼

class Solution:def trap(self, height: List[int]) -> int:n = len(height)left = [height[0]] * nright = [height[-1]] * nfor i in range(1, n):left[i] = max(left[i - 1], height[i])right[n - i - 1] = max(right[n - i], height[n - i - 1])res = 0for i in range(n):col = min(left[i], right[i]) - height[i]res += colreturn res

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

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

相關文章

面向對象,常用類,集合,異常,JDBC,mysql數據庫內容的復習,

1&#xff0c;面向對象 面向對象與面向過程對比 面向過程&#xff1a;關注過程&#xff0c;適合解決簡單直接的問題&#xff0c;代碼結構以函數為單位&#xff0c;如C語言。 面向對象&#xff1a;關注類&#xff0c;適合解決復雜問題更加適合解決復雜的項目中的問題等等&…

跨平臺編程:在Conda中搭建R語言環境的終極指南

&#x1f310; 跨平臺編程&#xff1a;在Conda中搭建R語言環境的終極指南 &#x1f310; 在數據科學和統計分析領域&#xff0c;R語言以其強大的數據處理能力和豐富的圖形表示功能而廣受歡迎。然而&#xff0c;對于習慣了使用Linux操作系統的用戶來說&#xff0c;如何方便地在…

【UML用戶指南】-23-對高級行為建模-狀態機

目錄 1、概述 2、狀態 2.1、狀態的組成 3、轉移 3.1、轉移的組成 4、高級狀態和轉移 4.1、進入效應和退出效應 4.2、內部轉移 4.3、do活動 4.4、延遲事件 4.5、子狀態機 5、子狀態 5.1、非正交子狀態 5.2、歷史狀態 5.3、正交子狀態 6、分叉與匯合 7、主動對象…

GOROOT GOPATH GOPROXY GO111MODULE

GOROOT GOROOT代表Go的安裝目錄。可執行程序go(或go.exe)和gofmt(或gofmt.exe)位于 GOROOT/bin目錄中。 配置GOROOT環境變量&#xff0c;其值為Go的安裝目錄&#xff1b;然后在環境變量PATH中添加GOROOT/bin路徑。 注意&#xff1a;GOROOT變量只是代表了安裝目錄&#xff0c;不…

泛型的實際應用示例

泛型的實際應用示例 1. 集合框架中的泛型 在Java的集合框架中&#xff0c;泛型被廣泛使用以確保類型安全并減少運行時錯誤。以下是一個使用泛型ArrayList的示例&#xff1a; java import java.util.ArrayList; import java.util.List; public class GenericCollectionsExamp…

【面試題】信息系統安全運維要做什么

信息系統安全運維是確保信息系統穩定、可靠、安全運行的一系列活動和措施。 其主要包括以下幾個方面&#xff1a; 1.系統監控&#xff1a; 實時監測信息系統的運行狀態&#xff0c;如服務器的性能指標、網絡流量、應用程序的運行情況等。通過監控工具&#xff0c;及時發現系統…

企業數據治理的下一步是數據資產管理?

隨著信息技術的飛速發展和數字化轉型的深入推進&#xff0c;企業數據已成為驅動業務增長和創新的核心要素。當企業數據治理工作取得顯著成效后&#xff0c;如何進一步發揮數據的價值&#xff0c;實現數據資產的有效管理&#xff0c;成為企業面臨的重要課題。 數據治理的基石作用…

算法練習——函數、遞歸和遞推

在此記錄一些有關函數、遞歸和遞推的問題。所有題目均來自洛谷的題單能力提升綜合題單Part1 入門階段 - 題單 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn) &#xff08;實際上都沒有用遞推做&#xff09; [NOIP2001 普及組] 數的計算 題目描述 給出正整數 n n n&#xf…

學習感悟丨在譽天學習數通HCIP怎么樣

大家好&#xff0c;我是譽天學員的徐同學&#xff0c;學習的數通HCIP課程。 在學校的時候&#xff0c;聽說下半年就要出去實習了&#xff0c;心中坎坷不安&#xff0c;現在我學到的知識遠遠不夠的。然后就想著學點東西充實一下自己的知識面和專業能力&#xff0c;有一次和同學談…

【漏洞復現】飛企互聯——SQL注入

聲明&#xff1a;本文檔或演示材料僅供教育和教學目的使用&#xff0c;任何個人或組織使用本文檔中的信息進行非法活動&#xff0c;均與本文檔的作者或發布者無關。 文章目錄 漏洞描述漏洞復現測試工具 漏洞描述 飛企互聯-FE企業運營管理平臺是一個基于云計算、智能化、大數據…

[圖解] 向量數據庫之何謂乘積量化器?

Product Quantization 在前面一節講解了向量數據庫索引相關的內容&#xff0c;那么本節將會講解其中壓縮方法的量化手段&#xff1a;乘積量化器。 簡單來說將向量的所有維度劃分為多個子空間&#xff0c;每個子空間一部分維度&#xff0c;然后每個子空間獨立去找最近距離。例如…

haproxy實現代理和負載均衡

HaProxy介紹&#xff1a; haproxy是法國開發者威利塔羅在2000年使用C語言開發的一個開源軟件&#xff0c;是一款具備高并發(一萬以上)、高性能的TCP和HTTP負載均衡器&#xff0c;支持基于cookie的持久性&#xff0c;自動故障切換&#xff0c;支持正則表達式及web狀態統計&…

Numpy array和Pytorch tensor的區別

1.Numpy array和Pytorch tensor的區別 筆記來源&#xff1a; 1.Comparison between Pytorch Tensor and Numpy Array 2.numpy.array 4.Tensors for Neural Networks, Clearly Explained!!! 5.What is a Tensor in Machine Learning? 1.1 Numpy Array Numpy array can only h…

arthas監控工具筆記(一)

文章目錄 啟動 math-game啟動 arthas查看 dashboard通過 thread 命令來獲取到math-game進程的 Main Class通過 jad 來反編譯 Main Class退出 arthas 界面linux服務器掛不上進程怎么辦? 核心表達式變量loader 本次調用類所在的 ClassLoaderclazz 本次調用類的 Class 引用method…

信息學奧賽初賽天天練-39-CSP-J2021基礎題-哈夫曼樹、哈夫曼編碼、貪心算法、滿二叉樹、完全二叉樹、前中后綴表達式轉換

PDF文檔公眾號回復關鍵字:20240629 2022 CSP-J 選擇題 單項選擇題&#xff08;共15題&#xff0c;每題2分&#xff0c;共計30分&#xff1a;每題有且僅有一個正確選項&#xff09; 5.對于入棧順序為a,b,c,d,e的序列&#xff0c;下列( )不合法的出棧序列 A. a&#xff0c;b&a…

螺旋矩陣問題C代碼

給定一個n行m列的二維數組&#xff0c;要求按順時針螺旋順序輸出矩陣中的所有元素&#xff0c;n和m小于等于10 如下圖是一個三行四列的螺旋矩陣 要求輸出 1 2 3 4 8 12 11 10 9 5 6 7 全局變量定義 int a[11][11]; int vis[11][11]; // 訪問標記數組關鍵代碼如下 int dx[] …

MySQL高級-MVCC-基本概念(當前讀、快照讀)

文章目錄 1、MVCC基本概念1.1、當前讀1.1.1、創建表 stu1.1.2、測試 1.2、快照讀 1、MVCC基本概念 全稱Multi-Version Concurrency Control&#xff0c;多版本并發控制。指維護一個數據的多個版本&#xff0c;使得讀寫操作沒有沖突&#xff0c;快照讀為MySQL實現MVCC提供了一個…

OpenCV cv::Mat到 Eigen 的正確轉換——cv2eigen

在進行計算機視覺項目時&#xff0c;我們經常需要處理相機位姿的變換。最近&#xff0c;我在項目中遇到了一個看似簡單但實際上頗具挑戰性的問題&#xff1a;從 OpenCV 的 cv::Mat 格式轉換到 Eigen 庫的格式。這個過程中遇到了一些問題&#xff0c;但最終找到了一個穩健的解決…

鏤空的文字?分享 1 段優質 CSS 代碼片段!

大家好&#xff0c;我是大澈&#xff01; 本文約 800 字&#xff0c;整篇閱讀約需 1 分鐘。 每日分享一段優質代碼片段。 今天分享一段優質 CSS 代碼片段&#xff0c;實現 CSS 文字鏤空的效果。 老規矩&#xff0c;先閱讀代碼片段并思考&#xff0c;再看代碼解析再思考&#…

nginx本地域名配置

修改hosts文件&#xff08;僅限本地測試&#xff09;&#xff1a; 在Windows上&#xff0c;hosts文件位于C:\Windows\System32\drivers\etc\hosts。 打開hosts文件&#xff0c;添加一行&#xff1a;127.0.0.1 xxx.com &#xff08;xxx.com為自己設定的域名&#xff09; 如果修…