LeetCode每日一題--407.接雨水②（困難）
2021.11.4，真是給我難的不輕
題目連結：https://leetcode-cn.com/problems/trapping-rain-water-ii/
1.題目描述
大早上起來看見困難題目，内心都已經涼了半截，哈哈
2.題目探讨
在我一開始看見這個題目的時候，我第一反應是使用單調棧，單調棧算法是維護一個遞增，或者遞減的棧，持續讀入資料，找到任意一個元素周圍比它大或者比它小的時間複雜度為O（N）的算法。具體可以看看這個部落格：https://zhuanlan.zhihu.com/p/101785785，是以這裡我一開始的想法：
初始做法:
- 在每一行保持一個單調遞減的棧，然後當找到下一個元素比目前的棧頂的元素大的時候，彈出棧頂元素，求出該元素和兩邊元素的內插補點的 最小值，然後在該元素所在列再次求一個單調棧，xxxx
缺點：
- 缺點也很明顯，時間複雜度太高，并且我在紙上模拟的過程中發現，可能有的塊是無法正常求出來的
tips：偷偷摸摸的看了題解
這道題要明确的兩個要點:
- 所給二維矩陣最外側的元素是無法儲存水的
- 儲水的塊，它的四周（可以延伸到最外側，并不一定是說它的上下左右四周）的塊高度比它高
那麼我們實際上選擇的做法是廣度優先算法，從最外層開始包圍這個矩陣，并且當一個塊儲存了水之後，它的高度就會發生變化，這個時候它就可以影響它周圍的塊
圖示（以給出的例一為例）：
在對外層使用優先隊列排序之後是這個樣子，我們保持隊列是升序排列，這樣我們每次總隊列頭部取出的元素就可以保證是目前最外層高度最小的元素，我們對于取出來的元素進行下列操作：
- 檢視四周是否有比自己高度小的，若存在-->則注水（因為目前彈出來的元素是包圍圈裡面高度最小的，這個還小，我們就可以注水了），若不存在-->将比自己高的加入隊列中，作為包圍圈
- 彈出這個元素，并且辨別這個元素已經周遊過了
代碼示範:
import java.util.PriorityQueue;
class Solution {
/*
* 明确兩個前提：
* - 四周的方塊不能儲存水
* - 方塊儲存水的時候，要比它周圍的方塊都低
*
* 1.取四周的點加入隊列
* */
public int trapRainWater(int[][] heightMap)
{
if(heightMap.length<=2||heightMap[0].length<=2)
return 0;
//row,col;
int row=heightMap.length,col=heightMap[0].length;
//建立visit數組
boolean [][]visit=new boolean[row][col];
//建立小頂堆,降序排列
PriorityQueue<int[]> pq=new PriorityQueue<>((o1,o2)->o1[1]-o2[1]);
//添加四周的元素，并且visit更改
for(int i=0;i<row;i++)
for(int j=0;j<col;j++)
{
if(i==0||j==0||i==row-1||j==col-1)
{
pq.offer(new int [] {i*col+j,heightMap[i][j]});
visit[i][j]=true;
}
}
int []dir= {-1,0,1,0,-1};
int res=0;
while(!pq.isEmpty())
{
int []cur=pq.poll();
int inx=cur[0]/col;
int iny=cur[0]%col;
for(int i=0;i<4;i++)
{
int opx=inx+dir[i];
int opy=iny+dir[i+1];
if(opx>0&&opx<row&&opy>0&&opy<col&&!visit[opx][opy])
{
if(heightMap[opx][opy]<cur[1])
{
res+=cur[1]-heightMap[opx][opy];
pq.offer(new int[]{opx*col+opy,cur[1]});
}
else {
pq.offer(new int[]{opx*col+opy,heightMap[opx][opy]});
}
visit[opx][opy]=true;
}
}
}
return res;
}
}
實話實說确實難，看了題解也看了好大一會，比我将的好的題解附帶上連結：
https://leetcode-cn.com/problems/trapping-rain-water-ii/solution/you-xian-dui-lie-de-si-lu-jie-jue-jie-yu-shui-ii-b/