其他:

今日總結
往期打卡

---

42. 接雨水

跳轉: 42. 接雨水

學習: 代碼隨想錄公開講解

問題:

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

思路:

單調棧的思路是只有遇到遞增時才有可能能兜住雨水
單調棧中記錄好右邊界(填充邊界之間的元素),如果當前柱子大于棧頂右邊界,就要用棧中前一個邊界或當前柱子中最小的那個填充洼地.
如果沒有前一個邊界,那么就說明前面都是已經填過的更小的值,兜不住雨水.

遍歷時一共有三種情況:
棧為空或當前比棧頂小
當前和棧頂一樣
當前大于棧頂
一樣就要更新右邊界,大于就開始出棧并填充

復雜度:

• 時間復雜度: $O(n)$
• 空間復雜度: $O(n)$

代碼:

class Solution {public int trap(int[] height) {Deque<Integer> stack = new LinkedList<>();int ans = 0;for(int i=0;i<height.length;i++){if(!stack.isEmpty()){if(height[stack.peekLast()]==height[i]){stack.pollLast();}else if(height[stack.peekLast()]<height[i]){do{int mid = stack.pollLast();if(!stack.isEmpty()){int h = Math.min(height[stack.peekLast()],height[i])-height[mid];int w = i - stack.peekLast()-1;ans+=h*w;}}while(!stack.isEmpty()&&height[stack.peekLast()]<height[i]);}}stack.add(i);}return ans;}
}

---

84. 柱狀圖中最大的矩形

跳轉: 84. 柱狀圖中最大的矩形

學習: 代碼隨想錄公開講解

問題:

給定 n 個非負整數，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。

求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。

思路:

如果遞減,就開始計算前面一直到和自己等高那一塊兒里的最大矩形.
再往后的計算不會和比當前元素高的部分合并,所以去掉的部分都會被看作當前元素.
為了讓最小的元素能從0算到i-1,需要在最開始加一個高度為0的最小的柱子(哪怕被更新了0高度本來也是不需要計算的)
最后一個元素添加完后形成的遞增棧也需要計算,可以從尾部再加一個為0的元素,將剩余可選矩陣全部計算求最大值

復雜度:

• 時間復雜度: $O(n)$
• 空間復雜度: $O(n)$

代碼:

class Solution {public int largestRectangleArea(int[] height) {Deque<Integer> stack = new LinkedList<>();int n = height.length+2;int[] heights = new int[n];System.arraycopy(height, 0, heights, 1, height.length);int ans = 0;stack.add(0);for(int i=1;i<n;i++){if(heights[i]>heights[stack.peekLast()]){stack.add(i);}else if(heights[i]==heights[stack.peekLast()]){stack.pollLast();stack.add(i);}else{while(!stack.isEmpty()&&heights[i]<=heights[stack.peekLast()]){int mid = stack.pollLast();if(!stack.isEmpty()){int w = i-stack.peekLast()-1;int h = heights[mid];ans = Math.max(ans,w*h);}}stack.add(i);}}return ans;}
}

---

98. 所有可達路徑

跳轉: 98. 所有可達路徑

學習: 代碼隨想錄公開講解

問題:

給定一個有 n 個節點的有向無環圖，節點編號從 1 到 n。請編寫一個函數，找出并返回所有從節點 1 到節點 n 的路徑。每條路徑應以節點編號的列表形式表示。

思路:

從1開始,dfs深搜路徑,回溯,結束條件是到達n,題目中說明了不會有平行邊和自環,所以深度有限不用擔心爆棧.
使用動態數組構造有向圖的鄰接矩陣,比使用基本數組要節省空間

復雜度:

• 時間復雜度: $O(m)$
• 空間復雜度: $O(m)$

代碼:

import java.util.*;class Main {static List<Integer>[] lists;static ArrayList<Integer> path = new ArrayList<>();static boolean flag = true;static void dfs(int start) {if(start==lists.length-1){flag = false;System.out.print(1);for(int i=0;i<path.size();i++){System.out.print(" "+path.get(i));}System.out.println("");return;}for(int i:lists[start]){path.add(i);dfs(i);path.remove(path.size()-1);}}public static void main(String[] args) {Scanner in = new Scanner(System.in);int N = in.nextInt();int M = in.nextInt();lists = new List[N + 1];for (int i = 0; i <= N; i++) {lists[i] = new ArrayList<>();}for (int i = 0; i < M; i++) {int x = in.nextInt();int y = in.nextInt();lists[x].add(y);}dfs(1);if(flag) System.out.println(-1);}
}

---

總結

練習了單調棧和DFS

往期打卡

代碼隨想錄算法訓練營第四十一天

代碼隨想錄算法訓練營第四十天

代碼隨想錄算法訓練營第三十九天

代碼隨想錄算法訓練營第三十八天

代碼隨想錄算法訓練營第三十七天

代碼隨想錄算法訓練營第三十五&三十六天

代碼隨想錄算法訓練營第三十四天

代碼隨想錄算法訓練營第三十三天(補)

代碼隨想錄算法訓練營第三十二天

代碼隨想錄算法訓練營第三十一天

代碼隨想錄算法訓練營第三十天(補)

代碼隨想錄算法訓練營第二十九天

代碼隨想錄算法訓練營第二十八天

代碼隨想錄算法訓練營第二十七天(補)

代碼隨想錄算法訓練營第二十六天

代碼隨想錄算法訓練營第二十五天

代碼隨想錄算法訓練營第二十四天

代碼隨想錄算法訓練營第二十三天

代碼隨想錄算法訓練營周末四

代碼隨想錄算法訓練營第二十二天(補)

代碼隨想錄算法訓練營第二十一天

代碼隨想錄算法訓練營第二十天

代碼隨想錄算法訓練營第十九天

代碼隨想錄算法訓練營第十八天

代碼隨想錄算法訓練營第十七天

代碼隨想錄算法訓練營周末三

代碼隨想錄算法訓練營第十六天

代碼隨想錄算法訓練營第十五天

代碼隨想錄算法訓練營第十四天

代碼隨想錄算法訓練營第十三天

代碼隨想錄算法訓練營第十二天

代碼隨想錄算法訓練營第十一天

代碼隨想錄算法訓練營周末二

代碼隨想錄算法訓練營第十天

代碼隨想錄算法訓練營第九天

代碼隨想錄算法訓練營第八天

代碼隨想錄算法訓練營第七天

代碼隨想錄算法訓練營第六天

代碼隨想錄算法訓練營第五天

代碼隨想錄算法訓練營周末一

代碼隨想錄算法訓練營第四天

代碼隨想錄算法訓練營第三天

代碼隨想錄算法訓練營第二天

代碼隨想錄算法訓練營第一天