前往
大廳
主題

[leetcode]407. Trapping Rain Water II

♙♲⚙\~O_O~/⚙♲♙ | 2021-08-12 12:00:01 | 巴幣 2 | 人氣 197

題目: 407. Trapping Rain Water II
難度: Hard
目前下列解法的時間複雜度:O(m*n*lg(m*n))


題目說明

給一 m*n 的數字矩陣,每個數字代表每一方格的高度。
問下雨時,最後能留住的水量。


解法

1. 對每一行與列分別求出1維時的蓄水量。(從頭滑到底取最高再滑回來)
2. 每1格取行列蓄水量的最小值。
3. 從水面最低者(們)開始,對每一格把旁邊凸起來的水挖掉。
4. sum(水高-方格高)


source code

32ms 的答案跟你說從外圍往裡面包,然後就直接算水高了


題外話

這是2016年寫的code


這是2021年寫的code


????

創作回應

熾炎之翼
越來越佬..
2021-08-12 12:16:46
♙♲⚙\~O_O~/⚙♲♙
其實還不夠
有些題目的時間複雜度我會多個lg(n),雖然會過,但看了別人的解答才知道我根本多做了一些事
2021-08-12 23:18:20

相關創作

更多創作