本文已收錄到 AndroidFamily，技術和職場問題，請關注公衆号 [彭旭銳] 提問。
大家好，我是小彭。
這場周賽是 LeetCode 雙周賽第 103 場，難得在五一假期第一天打周賽的人數也沒有少太多。這場比賽前 3 題比較簡單，我們把篇幅留給最後一題。
往期周賽回顧：LeetCode 單周賽第 342 場 · 容斥原理、計數排序、滑動視窗、子數組 GCB
周賽概覽
Q1. K 個元素的最大和（Easy）
簡單模拟題，不過多講解。
Q2. 找到兩個數組的字首公共數組（Medium）
簡單模拟題，在計數的實作上有三種解法：
- 解法 1：散清單 O(n) 空間複雜度
- 解法 2：技數數組 O(n) 空間複雜度
- 解法 3：狀态壓縮 O(1) 空間複雜度
Q3. 網格圖中魚的最大數目（Hard）
這道題的難度标簽是認真的嗎？打 Medium 都過分了居然打 Hard？
- 解法 1：BFS / DFS O(nm)
- 解法 2：并查集 O(nm)
Q4. 将數組清空（Hard）
這道題的難點在于如何想到以及正确地将原問題轉換為區間求和問題，思路想清楚後用樹狀數組實作。
- 解法 1：樹狀數組 + 索引數組 O(nlgn)
- 解法 2：樹狀數組 + 最小堆 O(nlgn)
Q1. K 個元素的最大和（Easy）
https://leetcode.cn/problems/maximum-sum-with-exactly-k-elements/
題目描述
給你一個下标從 0 開始的整數數組 nums 和一個整數 k 。你需要執行以下操作 恰好 k 次，最大化你的得分：
- 從 nums 中選擇一個元素 m 。
- 将選中的元素 m 從數組中删除。
- 将新元素 m + 1 添加到數組中。
- 你的得分增加 m 。
請你傳回執行以上操作恰好 k 次後的最大得分。
示例 1：
輸入：nums = [1,2,3,4,5], k = 3
輸出：18
解釋：我們需要從 nums 中恰好選擇 3 個元素并最大化得分。
第一次選擇 5 。和為 5 ，nums = [1,2,3,4,6] 。
第二次選擇 6 。和為 6 ，nums = [1,2,3,4,7] 。
第三次選擇 7 。和為 5 + 6 + 7 = 18 ，nums = [1,2,3,4,8] 。
是以我們傳回 18 。
18 是可以得到的最大答案。
示例 2：
輸入：nums = [5,5,5], k = 2
輸出：11
解釋：我們需要從 nums 中恰好選擇 2 個元素并最大化得分。
第一次選擇 5 。和為 5 ，nums = [5,5,6] 。
第二次選擇 6 。和為 6 ，nums = [5,5,7] 。
是以我們傳回 11 。
11 是可以得到的最大答案。
提示：
- 1 <= nums.length <= 100
- 1 <= nums[i] <= 100
- 1 <= k <= 100
預備知識 - 等差數列求和
- 等差數列求和公式：(首項 + 尾項) * 項數 / 2
題解（模拟 + 貪心）
顯然第一次操作的分數會選擇數組中的最大值 max，後續操作是以 max 為首項的等差數列，直接使用等差數列求和公式即可。
class Solution {
fun maximizeSum(nums: IntArray, k: Int): Int {
val max = Arrays.stream(nums).max().getAsInt()
return (max + max + k - 1) * k / 2
}
}
複雜度分析：
- 時間複雜度：O(n) 其中 n 是 nums 數組的長度；
- 空間複雜度：O(1)
Q2. 找到兩個數組的字首公共數組（Medium）
https://leetcode.cn/problems/find-the-prefix-common-array-of-two-arrays/
題目描述
給你兩個下标從 0 開始長度為 n 的整數排列 A 和 B 。
A 和 B 的 字首公共數組 定義為數組 C ，其中 C[i] 是數組 A 和 B 到下标為 i 之前公共元素的數目。
請你傳回 A 和 B 的 字首公共數組 。
如果一個長度為 n 的數組包含 1 到 n 的元素恰好一次，我們稱這個數組是一個長度為 n 的 排列 。
示例 1：
輸入：A = [1,3,2,4], B = [3,1,2,4]
輸出：[0,2,3,4]
解釋：i = 0：沒有公共元素，是以 C[0] = 0 。
i = 1：1 和 3 是兩個數組的字首公共元素，是以 C[1] = 2 。
i = 2：1，2 和 3 是兩個數組的字首公共元素，是以 C[2] = 3 。
i = 3：1，2，3 和 4 是兩個數組的字首公共元素，是以 C[3] = 4 。
示例 2：
輸入：A = [2,3,1], B = [3,1,2]
輸出：[0,1,3]
解釋：i = 0：沒有公共元素，是以 C[0] = 0 。
i = 1：隻有 3 是公共元素，是以 C[1] = 1 。
i = 2：1，2 和 3 是兩個數組的字首公共元素，是以 C[2] = 3 。
提示：
- 1 <= A.length == B.length == n <= 50
- 1 <= A[i], B[i] <= n
- 題目保證 A 和 B 兩個數組都是 n 個元素的排列。
題解一（散清單）
從左到右周遊數組，并使用散清單記錄通路過的元素，以及兩個數組交集：
class Solution {
fun findThePrefixCommonArray(A: IntArray, B: IntArray): IntArray {
val n = A.size
val ret = IntArray(n)
val setA = HashSet<Int>()
val setB = HashSet<Int>()
val interSet = HashSet<Int>()
for (i in 0 until n) {
setA.add(A[i])
setB.add(B[i])
if (setB.contains(A[i])) interSet.add(A[i])
if (setA.contains(B[i])) interSet.add(B[i])
ret[i] = interSet.size
}
return ret
}
}
複雜度分析：
- 時間複雜度：O(n) 其中 n 是 nums 數組的長度；
- 空間複雜度：O(n) 散清單空間。
題解二（計數數組）
題解一需要使用多倍空間，我們發現 A 和 B 都是 n 的排列，當通路到的元素 nums[i] 出現 2 次時就必然處于數組交集中。是以，我們不需要使用散清單記錄通路過的元素，而隻需要記錄每個元素出現的次數。
class Solution {
fun findThePrefixCommonArray(A: IntArray, B: IntArray): IntArray {
val n = A.size
val ret = IntArray(n)
val cnt = IntArray(n + 1)
var size = 0
for (i in 0 until n) {
if (++cnt[A[i]] == 2) size ++
if (++cnt[B[i]] == 2) size ++
ret[i] = size
}
return ret
}
}
複雜度分析：
- 時間複雜度：O(n) 其中 n 是 nums 數組的長度；
- 空間複雜度：O(n) 計數數組空間；
題解三（狀态壓縮）
既然 A 和 B 的元素值不超過 50，我們可以使用兩個 Long 變量代替散清單優化空間複雜度。
class Solution {
fun findThePrefixCommonArray(A: IntArray, B: IntArray): IntArray {
val n = A.size
val ret = IntArray(n)
var flagA = 0L
var flagB = 0L
var size = 0
for (i in 0 until n) {
flagA = flagA or (1L shl A[i])
flagB = flagB or (1L shl B[i])
// Kotlin 1.5 才有 Long.countOneBits()
// ret[i] = (flagA and flagB).countOneBits()
ret[i] = java.lang.Long.bitCount(flagA and flagB)
}
return ret
}
}
複雜度分析：
- 時間複雜度：O(n) 其中 n 是 nums 數組的長度；
- 空間複雜度：O(1) 僅使用常量級别空間；
Q3. 網格圖中魚的最大數目（Hard）
https://leetcode.cn/problems/maximum-number-of-fish-in-a-grid/description/
題目描述
給你一個下标從 0 開始大小為 m x n 的二維整數數組 grid ，其中下标在 (r, c) 處的整數表示：
- 如果 grid[r][c] = 0 ，那麼它是一塊 陸地 。
- 如果 grid[r][c] > 0 ，那麼它是一塊 水域 ，且包含 grid[r][c] 條魚。
一位漁夫可以從任意 水域 格子 (r, c) 出發，然後執行以下操作任意次：
- 捕撈格子 (r, c) 處所有的魚，或者
- 移動到相鄰的 水域 格子。
請你傳回漁夫最優政策下， 最多 可以捕撈多少條魚。如果沒有水域格子，請你傳回 0 。
格子 (r, c) 相鄰 的格子為 (r, c + 1) ，(r, c - 1) ，(r + 1, c) 和 (r - 1, c) ，前提是相鄰格子在網格圖内。
示例 1：
輸入：grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]
輸出：7
解釋：漁夫可以從格子(1,3) 出發，捕撈 3 條魚，然後移動到格子(2,3) ，捕撈 4 條魚。
示例 2：
輸入：grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]
輸出：1
解釋：漁夫可以從格子 (0,0) 或者 (3,3) ，捕撈 1 條魚。
提示：
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 10
- 0 <= grid[i][j] <= 10
問題抽象
求 “權重連通分量 / 島嶼問題”，用二維 BFS 或 DFS 或并查集都可以求出所有連通塊的最大值，史上最水 Hard 題。
題解一（二維 DFS）
class Solution {
private val directions = arrayOf(intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0))
fun findMaxFish(grid: Array<IntArray>): Int {
var ret = 0
for (i in 0 until grid.size) {
for (j in 0 until grid[0].size) {
ret = Math.max(ret, dfs(grid, i, j))
}
}
return ret
}
private fun dfs(grid: Array<IntArray>, i: Int, j: Int): Int {
if (grid[i][j] <= 0) return 0
var cur = grid[i][j]
grid[i][j] = -1
for (direction in directions) {
val newI = i + direction[0]
val newJ = j + direction[1]
if (newI < 0 || newI >= grid.size || newJ < 0 || newJ >= grid[0].size || grid[newI][newJ] <= 0) continue
cur += dfs(grid, newI, newJ)
}
return cur
}
}
複雜度分析：
- 時間複雜度：O(nm) 其中 n 和 m 是 grid 數組的行和列；
- 空間複雜度：O(n + m) 遞歸棧的最大深度。
題解二（并查集）
附贈一份并查集的解法：
class Solution {
private val directions = arrayOf(intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0))
fun findMaxFish(grid: Array<IntArray>): Int {
val n = grid.size
val m = grid[0].size
var ret = 0
// 并查集
val helper = UnionFind(grid)
// 合并
for (i in 0 until n) {
for (j in 0 until m) {
ret = Math.max(ret, grid[i][j])
if (grid[i][j] <= 0) continue
for (direction in directions) {
val newI = i + direction[0]
val newJ = j + direction[1]
if (newI < 0 || newI >= grid.size || newJ < 0 || newJ >= grid[0].size || grid[newI][newJ] <= 0) continue
ret = Math.max(ret, helper.union(i * m + j, newI * m + newJ))
}
}
}
// helper.print()
return ret
}
private class UnionFind(private val grid: Array<IntArray>) {
private val n = grid.size
private val m = grid[0].size
// 父節點
private val parent = IntArray(n * m) { it }
// 高度
private val rank = IntArray(n * m)
// 數值
private val value = IntArray(n * m)
init {
for (i in 0 until n) {
for (j in 0 until m) {
value[i * m + j] = grid[i][j]
}
}
}
// return 子集的和
fun union(x: Int, y: Int): Int {
// 按秩合并
val parentX = find(x)
val parentY = find(y)
if (parentX == parentY) return value[parentY]
if (rank[parentX] < rank[parentY]) {
parent[parentX] = parentY
value[parentY] += value[parentX]
return value[parentY]
} else if (rank[parentY] < rank[parentX]) {
parent[parentY] = parentX
value[parentX] += value[parentY]
return value[parentX]
} else {
parent[parentY] = parentX
value[parentX] += value[parentY]
rank[parentY]++
return value[parentX]
}
}
fun print() {
println("parent=${parent.joinToString()}")
println("rank=${rank.joinToString()}")
println("value=${value.joinToString()}")
}
private fun find(i: Int): Int {
// 路徑壓縮
var x = i
while (parent[x] != x) {
parent[x] = parent[parent[x]]
x = parent[x]
}
return x
}
}
}
複雜度分析：
- 時間複雜度：O(nm) 其中 n 和 m 是 grid 數組的行和列；
- 空間複雜度：O(n + m) 遞歸棧的最大深度。
相似題目：
- 130. 被圍繞的區域
- 200. 島嶼數量
- 990. 等式方程的可滿足性
推薦閱讀：
- 如何使用并查集解決朋友圈問題？
Q4. 将數組清空（Hard）
https://leetcode.cn/problems/make-array-empty/
題目描述
給你一個包含若幹 互不相同 整數的數組 nums ，你需要執行以下操作 直到數組為空 ：
- 如果數組中第一個元素是目前數組中的 最小值 ，則删除它。
- 否則，将第一個元素移動到數組的 末尾 。
請你傳回需要多少個操作使 nums 為空。
示例 1：
輸入：nums = [3,4,-1]
輸出：5
OperationArray1[4, -1, 3]2[-1, 3, 4]3[3, 4]4[4]5[]
示例 2：
輸入：nums = [1,2,4,3]
輸出：5
OperationArray1[2, 4, 3]2[4, 3]3[3, 4]4[4]5[]
示例 3：
輸入：nums = [1,2,3]
輸出：3
OperationArray1[2, 3]2[3]3[]
提示：
- 1 <= nums.length <= 105
- 109 <= nums[i] <= 109
- nums 中的元素 互不相同 。
預備知識 - 循環數組
循環數組：将數組尾部元素的後繼視為數組首部元素，數組首部元素的前驅視為數組尾部元素。
預備知識 - 樹狀數組
OI · 樹狀數組
樹狀數組也叫二叉索引樹（Binary Indexed Tree），是一種支援 “單點修改” 和 “區間查詢” 的代碼量少的資料結構。相比于線段樹來說，樹狀數組的代碼量遠遠更少，是一種精妙的資料結構。
樹狀數組核心思想是将數組 [0,x] 的字首和拆分為不多于 logx 段非重疊的區間，在計算字首和時隻需要合并 logx 段區間資訊，而不需要合并 n 個區間資訊。同時，在更新單點值時，也僅需要修改 logx 段區間，而不需要（像字首和數組）那樣修改 n 個資訊。可以說，樹狀數組平衡了單點修改和區間和查詢的時間複雜度：
- 單點更新 add(index,val)：将序列第 index 位元素增加 val，時間複雜度為 O(lgn)，同時對應于在邏輯樹形結構上從小分塊節點移動到大分塊節點的過程（修改元素會影響大分塊節點（子節點）的值）；
- 區間查詢 prefixSum(index)：查詢前 index 個元素的字首和，時間複雜度為 O(lgn)，同時對應于在邏輯樹形結構上累加區間段的過程。
樹狀數組
問題結構化
1、概括問題目标
求消除數組的操作次數。
2、分析題目要件
- 觀察：在每次操作中，需要觀察數組首部元素是否為剩餘元素中的最小值。例如序列 [3,2,1] 的首部元素不是最小值；
- 消除：在每次操作中，如果數組首部元素是最小值，則可以消除數組頭部元素。例序列 [1,2,3] 在一次操作後變為 [2,3]；
- 移動：在每次操作中，如果數組首部元素不是最小值，則需要将其移動到數組末尾。例如序列 [3,2,1] 在一次操作後變為 [2,1,3]。
3、觀察資料特征
- 資料量：測試用例的資料量上界為 10^5，這要求我們實作低于 O(n^2) 時間複雜度的算法才能通過；
- 資料大小：測試用例的資料上下界為 [-10^9, 10^9]，這要求我們考慮大數問題。
4、觀察測試用例
以序列 [3,4,-1] 為例，一共操作 5 次：
- [3,4,-1]：-1 是最小值，将 3 和 4 移動到末尾後才能消除 -1，一共操作 3 次；
- [3,4]：3 是最小值，消除 3 操作 1 次；
- [4]：4 是最小值，消除 4 操作 1 次；
5、提高抽象程度
- 序列：線性表是由多個元素組成的序列，除了數組的頭部和尾部元素之外，每個元素都有一個前驅元素和後繼元素。在将數組首部元素移動到數組末尾時，将改變數組中的部分元素的關系，即原首部元素的前驅變為原尾部元素，原尾部元素的後繼變為原首部元素。
- 是否為決策問題：由于每次操作的行為是固定的，是以這道題隻是純粹的模拟問題，并不是決策問題。
6、具體化解決手段
消除操作需要按照元素值從小到大的順序删除，那麼如何判斷數組首部元素是否為最小值？
- 手段 1（暴力枚舉）：枚舉數組剩餘元素，判斷首部元素是否為最小值，單次判斷的時間複雜度是 O(n)；
- 手段 2（排序）：對原始數組做預處理排序，由于原始數組的元素順序資訊在本問題中是至關重要的，是以不能對原始數組做原地排序，需要借助輔助資料結構，例如索引數組、最小堆，單次判斷的均攤時間複雜度是 O(1)。
如何表示元素的移動操作：
- 手段 1（數組）：使用數組塊狀複制 Arrays.copy()，單次操作的時間複雜度是 O(n)；
- 手段 2（雙向連結清單）：将原始數組轉換為雙向連結清單，操作連結清單首尾元素的時間複雜度是 O(1)，但會消耗更多空間；
如何解決問題：
- 手段 1（模拟）：模拟消除和移動操作，直到數組為空。在最壞情況下（降序數組）需要操作 n^2 次，是以無論如何都是無法滿足題目的資料量要求；
至此，問題陷入瓶頸。
解決方法是重複「分析問題要件」-「具體化解決手段」的過程，枚舉掌握的算法、資料結構和 Tricks 尋找突破口：
表示元素的移動操作的新手段：
- 手段 3（循環數組）：将原數組視為循環數組，數組尾部元素的後繼是數組首部元素，數組首部元素的前驅是數組尾部元素，不再需要實際性的移動操作。
解決問題的新手段：
- 手段 2（計數）：觀察測試用例發現，消除每個元素的操作次數取決于該元素的前驅中未被消除的元素個數，例如序列 [3,4,-1] 中 -1 前有 2 個元素未被删除，是以需要 2 次操作移動 3 和 4，再增加一次操作消除 -1。那麼，我們可以定義 rangeSum(i,j) 表示區間 [i,j] 中未被删除的元素個數，每次消除操作隻需要查詢上一次的消除位置（上一個最小值）與目前的消除位置（目前的最小值）中間有多少個數字未被消除 rangeSum(上一個最小值位置, 目前的最小值位置)，這個區間和就是消除目前元素需要的操作次數。
區分上次位置與目前位置的前後關系，需要分類讨論：
- id < preId：消除次數 = rangeSum(id, preId)
- id > preId：消除次數 = rangeSum(-1, id) + rangeSum(preId,n - 1)
如何實作手段 2（計數）：
在代碼實作上，涉及到「區間求和」和「單點更新」可以用線段數和樹狀數組實作。樹狀數組的代碼量遠比線段樹少，是以我們選擇後者。
示意圖
答疑：
- 消除每個元素的操作次數不用考慮前驅元素中小于目前元素的元素嗎？
由于消除是按照元素值從小到大的順序消除的，是以未被消除的元素一定比目前元素大，是以我們不強調元素大小關系。
題解一（樹狀數組 + 索引數組）
- 使用「樹狀數組」的手段解決區間和查詢和單點更新問題，注意樹狀數組是 base 1 的；
- 使用「索引數組」的手段解決排序 / 最小值問題。
class Solution {
fun countOperationsToEmptyArray(nums: IntArray): Long {
val n = nums.size
var ret = 0L
// 索引數組
val ids = Array<Int>(n) { it }
// 排序
Arrays.sort(ids) { i1, i2 ->
// 考慮大數問題
// nums[i1] - nums[i2] x
if (nums[i1] < nums[i2]) -1 else 1
}
// 樹狀數組
val bst = BST(n)
// 上一個被删除的索引
var preId = -1
// 周遊索引
for (id in ids) {
// 區間和
if (id > preId) {
ret += bst.rangeSum(preId, id)
// println("id=$id, ${bst.rangeSum(preId, id)}")
} else {
ret += bst.rangeSum(-1, id) + bst.rangeSum(preId, n - 1)
// println("id=$id, ${bst.rangeSum(-1,id)} + ${bst.rangeSum(preId, n - 1)}")
}
// 單點更新
bst.dec(id)
preId = id
}
return ret
}
// 樹狀數組
private class BST(private val n: Int) {
// base 1
private val data = IntArray(n + 1)
init {
// O(nlgn) 建樹
// for (i in 0 .. n) {
// update(i, 1)
// }
// O(n) 建樹
for (i in 1 .. n) {
data[i] += 1
val parent = i + lowbit(i)
if (parent <= n) data[parent] += data[i]
}
}
fun rangeSum(i1: Int, i2: Int): Int {
return preSum(i2 + 1) - preSum(i1 + 1)
}
fun dec(i: Int) {
update(i + 1, -1)
}
private fun preSum(i: Int): Int {
var x = i
var sum = 0
while (x > 0) {
sum += data[x]
x -= lowbit(x)
}
return sum
}
private fun update(i: Int, delta: Int) {
var x = i
while (x <= n) {
data[x] += delta
x += lowbit(x)
}
}
private fun lowbit(x: Int) = x and (-x)
}
}
複雜度分析：
- 時間複雜度：O(nlgn) 其中 n 是 nums 數組的長度，排序 O(nlgn)、樹狀數組建樹 O(n)、單次消除操作的區間和查詢和單點更新的時間為 O(lgn)；
- 空間複雜度：O(n) 索引數組空間 + 樹狀數組空間。
題解二（樹狀數組 + 最小堆）
附贈一份最小堆排序的代碼：
- 使用「樹狀數組」的手段解決區間和查詢和單點更新問題，注意樹狀數組是 base 1 的；
- 使用「最小堆」的手段解決排序 / 最小值問題。
class Solution {
fun countOperationsToEmptyArray(nums: IntArray): Long {
val n = nums.size
var ret = 0L
// 最小堆
val ids = PriorityQueue<Int>() { i1, i2 ->
if (nums[i1] < nums[i2]) -1 else 1
}
for (id in 0 until n) {
ids.offer(id)
}
// 樹狀數組
val bst = BST(n)
// 上一個被删除的索引
var preId = -1
// 周遊索引
while (!ids.isEmpty()) {
val id = ids.poll()
// 區間和
if (id > preId) {
ret += bst.rangeSum(preId, id)
} else {
ret += bst.rangeSum(-1, id) + bst.rangeSum(preId, n - 1)
}
// 單點更新
bst.dec(id)
preId = id
}
return ret
}
}
複雜度分析：
- 時間複雜度：O(nlgn) 其中 n 是 nums 數組的長度，堆排序 O(nlgn)、樹狀數組建樹 O(n)、單次消除操作的區間和查詢和單點更新的時間為 O(lgn)；
- 空間複雜度：O(n) 堆空間 + 樹狀數組空間。
相似題目：
- 315. 計算右側小于目前元素的個數
- 1040. 移動石子直到連續 II
往期回顧
- LeetCode 單周賽第 342 場 · 把問題學複雜，再學簡單
- LeetCode 單周賽第 341 場· 難度上來了，圖論的問題好多啊！
- LeetCode 雙周賽第 102 場· 這次又是最短路。
- LeetCode 雙周賽第 101 場 · 是時候做出改變了！