難度: Hard
目前下列解法的時間複雜度:O(m*n*lg(m*n))
題目說明
給一 m*n 的數字矩陣,每個數字代表每一方格的高度。
問下雨時,最後能留住的水量。
解法
1. 對每一行與列分別求出1維時的蓄水量。(從頭滑到底取最高再滑回來)
2. 每1格取行列蓄水量的最小值。
3. 從水面最低者(們)開始,對每一格把旁邊凸起來的水挖掉。
4. sum(水高-方格高)
source code
32ms 的答案跟你說從外圍往裡面包,然後就直接算水高了
題外話
這是2016年寫的code
這是2021年寫的code
????