Hoi hoi！
我是 @nyaomaru，一位前端工程師，最近沉迷拉麵。😸🍜
你已經用過 DSA View View 了嗎？👀👀
https://dev.to/nyaomaru/i-built-a-tool-to-visualize-dsa-lets-learn-together-dsa-view-view--djo
DSA View View 可以透過視覺化你實作的實際執行過程，幫助你理解 DSA。
在前幾篇文章中，我們看過這些題目：
- Two Sum
- Binary Search
- Bubble Sort
- Valid Parentheses
- Reverse Linked List
- Maximum Depth of Binary Tree
- Number of Islands
- Invert Binary Tree
- Course Schedule
這次，讓我們再來試三題：
- Trapping Rain Water
- Top K Frequent Elements
- Selection Sort
這三題都帶出了幾種很實用的思考方式
從兩側同時縮小問題
先計數，再依頻率整理
反覆選出下一個值同樣地，這些實作不一定很龐大。
但有一些會變動的值，我們必須一直放在腦中。
所以與其只讀最後的程式碼，
不如看看實際發生了什麼。👀👀
🌧️ Trapping Rain Water
先從 Trapping Rain Water 開始。
假設我們有這些高度
[0, 1, 0, 2, 1, 0, 1, 3]如果把它們畫成牆，大概會像這樣。
█
█ █
█ █ █ █ █
-----------------
0 1 0 2 1 0 1 3雨水從上方落下。
有些水會流走。
但有些水會被較高的牆困住。
例如
█~~~~~~~█
█~~~█~~~~~~~█
-----------------所以問題是：
能接住多少水？
一開始我覺得這題非常令人困惑。😿
因為某個位置上方能存多少水，取決於別的地方的牆。
那我們到底需要哪些資訊呢？
某個位置上方能裝多少水？
想像這個位置
left wall right wall
█ █
█ x █
█ █ █水位不可能高過較矮的那一側。
所以可達到的最高水位是
Math.min(leftMax, rightMax);再減掉目前高度。
概念上就是：
water = min(leftMax, rightMax) - currentHeight這就是基本想法。
但我們真的需要對每個位置都重新算左右兩邊嗎？
不用。
我們可以用 雙指標。
雙指標
下面是實作。
function trap(height: number[]): number {
let left = 0;
let right = height.length - 1;
let leftMax = 0;
let rightMax = 0;
let water = 0;
while (left <= right) {
if (height[left] <= height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
water += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
right--;
}
}
return water;
}這裡有幾個重要的值。
left
right
leftMax
rightMax
water這正是那種我會把每個變數都看懂，
但最後卻無法把它們一起掌握的程式。😹
讓我們用一個小一點的例子來追蹤。
[2, 0, 1, 3]從兩端開始
一開始
left = 0
right = 3
[2, 0, 1, 3]
↑ ↑
left right高度分別是：
height[left] = 2
height[right] = 3因為
2 <= 3所以我們處理左邊。
左邊有一堵高度 2 的牆。
因此
leftMax = 2然後把 left 往右移。
[2, 0, 1, 3]
↑ ↑
left right現在可以裝水了
目前高度是
0但我們已經知道左邊有一堵高度 2 的牆。
而且右邊目前至少跟它一樣高。
所以這個位置可以裝
leftMax - height[left]
= 2因此
water = 2再往前移一次。
[2, 0, 1, 3]
↑ ↑
left right現在
height[left] = 1
leftMax = 2所以
2 - 1 = 1再多一單位的水。
water = 3最後我們會走到最終那堵牆。
完成！🎉
為什麼可以先處理較矮的一側？
這部分是重點。
假設
height[left] <= height[right]那我們已經知道右邊有一堵至少跟目前左牆一樣高的牆。
所以對目前左側位置來說，限制因素就是我們從左邊看過的最高牆。
因此我們可以安全地計算
leftMax - height[left];而不需要知道所有未來的牆。
右邊的邏輯也一樣。
如果
height[right] < height[left]我們就用 rightMax 處理右邊。
因此演算法會持續把未知區域往中間縮小
L → → → ← ← ← R直到全部處理完。
複雜度
每個指標都只會沿著陣列走一遍。
時間：O(n)
空間：O(1)👀 來用 View View 看看
這題很適合拿來說明我為什麼喜歡視覺化。
程式裡有這些值：
left
right
leftMax
rightMax
water而且它們是不同時間點變動的。
當我只看這行：
water += leftMax - height[left];我可能會想：
- 為什麼這裡用
leftMax？ - 現在
rightMax是多少？ - 為什麼移動的是
left而不是right？ - 我們已經算進多少水了？
- 哪一段陣列還沒處理？
😿
一步一步看下去，就能真正看到搜尋區域逐漸縮小。
L R
↓ ↓
[2, 0, 1, 3]
L R
↓ ↓
[2, 0, 1, 3]
L R
↓ ↓
[2, 0, 1, 3]同時
leftMax
rightMax
water也在不斷改變。
這個演算法其實是在問：
我現在可以安全地先解哪一邊？
然後把那一邊解掉，再往內縮。🌧️😸
🔢 Top K Frequent Elements
接著來找 Top K Frequent Elements。
假設我們有
[1, 1, 1, 2, 2, 3]以及
k = 2每個數字出現幾次？
1 → 3 次
2 → 2 次
3 → 1 次所以出現次數最多的兩個值是
[1, 2]很簡單吧。
但要怎麼實作呢？
先把所有數字都數一遍
我們首先需要的是頻率。
可以使用 Map。
const frequency = new Map<number, number>();接著把每個值的次數加上去。
for (const num of nums) {
frequency.set(num, (frequency.get(num) ?? 0) + 1);
}對於
[1, 1, 1, 2, 2, 3]我們會得到
frequency = {
1 → 3
2 → 2
3 → 1
}很好。
但我們還需要 Top K。
當然，我們可以依照頻率把所有東西排序。
不過還有另一個很有趣的方法。
把頻率當作索引
最大可能的頻率是
nums.length所以我們可以建立桶子。
const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []);索引代表頻率。
例如
bucket[1] = 出現 1 次的值
bucket[2] = 出現 2 次的值
bucket[3] = 出現 3 次的值以這個例子來說：
frequency = {
1 → 3
2 → 2
3 → 1
}桶子會變成
index 0 → []
index 1 → [3]
index 2 → [2]
index 3 → [1]這真的很有意思。👀👀
與其問：
這個數字的頻率是多少？
我們反過來想：
哪些數字有這個頻率？
實作
完整實作如下：
function topKFrequent(nums: number[], k: number): number[] {
const frequency = new Map<number, number>();
for (const num of nums) {
frequency.set(num, (frequency.get(num) ?? 0) + 1);
}
const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []);
for (const [num, count] of frequency) {
buckets[count].push(num);
}
const result: number[] = [];
for (let count = buckets.length - 1; count >= 0; count--) {
for (const num of buckets[count]) {
result.push(num);
if (result.length === k) {
return result;
}
}
}
return result;
}讓我們跟著流程看。
第 1 步：建立頻率表
一開始
frequency = {}讀到第一個 1。還有另一個，再一個...
1 → 1
1 → 2
1 → 3接著是 2。再一個。
1 → 3
2 → 1
2 → 2最後是 3。
1 → 3
2 → 2
3 → 1完成。
第 2 步：把值放進桶子
現在
buckets[count].push(num);對
1 → 3我們做
buckets[3].push(1)對
2 → 2我們做
buckets[2].push(2)而
3 → 1則變成
buckets[1].push(3)所以最後會是
0: []
1: [3]
2: [2]
3: [1]第 3 步：從最高頻率開始讀
我們要的是 出現次數最多 的值。
所以不要從 0 開始，要從最後面開始。
3 → [1]
2 → [2]
1 → [3]先拿 1。
result = [1]還差一個。往下走。
拿 2。
result = [1, 2]現在
result.length === k所以直接回傳。
完成！🎉
為什麼這招有趣？
我喜歡這個解法，是因為第二個結構改變了我們看問題的角度。
Map 表示：
值 → 頻率桶子表示：
頻率 → 值資訊一樣，但方向不同。
然後找最高頻率的值就變簡單了。
只要從桶子後面往前走即可。
複雜度
我們把每個數字都數一次。
再把每個不同的值分配到桶子裡。
最後再掃過桶子。
時間：O(n)
空間：O(n)👀 來用 View View 看看
這裡有兩個轉換過程。
首先
nums
↓
frequency Map接著
frequency Map
↓
buckets然後
buckets
↓
result只看最終實作，很容易忽略為什麼要建立兩個不同的資料結構。
有了執行過程可視化之後，我們就能看著資料改變形狀。
[1, 1, 1, 2, 2, 3]
↓ count
1 → 3
2 → 2
3 → 1
↓ bucket
1: [3]
2: [2]
3: [1]
↓ highest first
[1, 2]這就是我喜歡的地方。
我們不是魔法般地直接找出 Top K。
而是把資訊重新整理，直到答案變得一目了然。🔢😸
👉 Selection Sort
最後，再來排一次序吧！
我們在前一篇文章已經看過 Bubble Sort。
這次來試試 Selection Sort。
假設我們有
[5, 3, 4, 1, 2]我們想要的是
[1, 2, 3, 4, 5]Selection Sort 的想法非常簡單：
找到剩餘值中最小的，然後把它放到前面。
接著重複。
第一次掃描
一開始
[5, 3, 4, 1, 2]
↑
i先假設第一個值目前是最小的。
minIndex = 0接著往右掃描所有元素。
5 vs 33 比較小。
所以：
minIndex = 1然後：
3 vs 4不變。
接著：
3 vs 11 比較小。
minIndex = 3最後：
1 vs 2還是 1。
所以最小值在索引 3。
交換
[5, 3, 4, 1, 2]
↑ ↑
i min↓
[1, 3, 4, 5, 2]現在第一個位置完成了。
[1 | 3, 4, 5, 2]
↑
sorted重複
接著從索引 1 開始。
[1 | 3, 4, 5, 2]
↑
i找出
[3, 4, 5, 2]中的最小值。
是 2。
交換。
[1, 2 | 4, 5, 3]再來一次。
找出剩餘區間最小值。
3最後會變成
[1, 2, 3, 4, 5]排序完成！🎉
實作
function selectionSort(nums: number[]): number[] {
for (let i = 0; i < nums.length - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
if (minIndex !== i) {
[nums[i], nums[minIndex]] = [nums[minIndex], nums[i]];
}
}
return nums;
}這裡有兩個重要的索引：
i
minIndex另外還有
j它負責在未排序區域中搜尋。
為什麼叫 Selection Sort？
因為每一輪都會 選出 剩餘值中最小的那個。
找最小值
↓
選出它
↓
移到前面
↓
重複這基本上就是整個演算法。
複雜度
對於每個位置，我們都要掃描剩餘的值。
所以：
時間：O(n²)而且是原地排序。
空間：O(1)Selection Sort 當然不是我平常會拿來排序大型正式資料集的選擇。😹
但作為學習用的演算法，它非常適合視覺化。
👀 來用 View View 看看
這個實作包含巢狀迴圈。
for (let i = 0; i < nums.length - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < nums.length; j++) {讀著讀著，我可能會開始搞不清楚：
- 哪一段已經排序好了？
i在哪裡？j在哪裡？minIndex目前指向誰？- 什麼時候才會交換？
當我們把它視覺化後，基本模式就一目了然了。
[5, 3, 4, 1, 2]
↑
smallest
[1 | 3, 4, 5, 2]
↑
smallest
[1, 2 | 4, 5, 3]演算法會不斷從左到右建立已完成的區域。
這就是 Selection Sort。
選出剩餘值中最小的。
把它放到下一個位置。然後重複。🍥😸
🧠 我們到底學到了什麼？
再一次，這三題看起來完全不同。
但它們都帶出了一種有用的思考方式。
Trapping Rain Water
利用兩側資訊，判斷哪一部分已經可以安全地處理。
我現在對哪一側了解得夠多？Top K Frequent Elements
有時候，先計數只是第一步。
把資料重新整理成更容易取答案的結構。
我能不能把這些資訊重新組織成我真正需要的樣子？Selection Sort
一次確定一個永久位置，逐步建立答案。
這個位置下一個應該放什麼值？所以這次我們看到了
雙指標
頻率桶
選擇又是三種不同的心智模型。
而且就像前面的題目一樣，困難的地方通常不是語法。
而是狀態一直在變。
哪個指標移動了？
現在最大值是多少？
Map 裡面有什麼？
哪個桶子變了？
minIndex 在哪？
哪一段已經完成？腦中要記住的東西很多。
所以我更想要的是把它看出來。👀👀
🎯 結語
這篇文章我們看了：
- 用雙指標解 Trapping Rain Water
- 用頻率桶解 Top K Frequent Elements
- 用 Selection Sort 排序
更重要的是，我們追蹤了它們在執行時狀態如何變化。
在 Trapping Rain Water 中，我們看到兩個指標向內移動，同時 leftMax、rightMax 和 water 不斷改變。
left → ← right在 Top K Frequent Elements 中，我們看到同一份資料改變了表示方式。
array
↓
frequency Map
↓
buckets
↓
result在 Selection Sort 中，我們看到已排序區域一格一格往右擴張。
這正是我打造 DSA View View 的原因。
https://dsa-view-view.vercel.app
你可以撰寫或載入 TypeScript 實作，用自己的輸入來執行，並在執行過程中前後移動查看。
如果你也在學 DSA，試著一步一步看一題吧。
如果你還有想要我下一篇介紹的 DSA 題目，也請在留言告訴我！
我自己也還有很多演算法要學。😸
一起鍛鍊我們的 DSA 肌肉吧！💪
如果你喜歡 DSA View View，請幫它點個星星 ⭐
https://github.com/nyaomaru/dsa-view-view
我們下一篇文章見！
1) --- 會變成分隔線（上一行必須是空白）
2) # 會變成一級標題
3) ## 會變成二級標題
4) ### 會變成三級標題
5) **粗體文字**會顯示粗體文字
6) ```當第一行與最後一行會顯示程式碼
7) 請搜尋 Markdown 語法，了解各種格式
