本文已收錄到 AndroidFamily，技術(shù)和職場(chǎng)問(wèn)題，請(qǐng)關(guān)注公眾號(hào) [彭旭銳] 提問(wèn)。

大家好，我是小彭。

這場(chǎng)周賽是 LeetCode 雙周賽第 103 場(chǎng)，難得在五一假期第一天打周賽的人數(shù)也沒(méi)有少太多。這場(chǎng)比賽前 3 題比較簡(jiǎn)單，我們把篇幅留給最后一題。

往期周賽回顧：LeetCode 單周賽第 342 場(chǎng) · 容斥原理、計(jì)數(shù)排序、滑動(dòng)窗口、子數(shù)組 GCB

周賽概覽

Q1.?K 個(gè)元素的最大和（Easy）

簡(jiǎn)單模擬題，不過(guò)多講解。

Q2.?找到兩個(gè)數(shù)組的前綴公共數(shù)組（Medium）

簡(jiǎn)單模擬題，在計(jì)數(shù)的實(shí)現(xiàn)上有三種解法：

• 解法 1：散列表 $O(n)$ 空間復(fù)雜度
• 解法 2：技數(shù)數(shù)組 $O(n)$ 空間復(fù)雜度
• 解法 3：狀態(tài)壓縮 $O(1)$ 空間復(fù)雜度

Q3.?網(wǎng)格圖中魚(yú)的最大數(shù)目（Hard）

這道題的難度標(biāo)簽是認(rèn)真的嗎？打 Medium 都過(guò)分了居然打 Hard？

• 解法 1：BFS / DFS $O(nm)$
• 解法 2：并查集 $O(nm)$

Q4.?將數(shù)組清空（Hard）

這道題的難點(diǎn)在于如何想到以及正確地將原問(wèn)題轉(zhuǎn)換為區(qū)間求和問(wèn)題，思路想清楚后用樹(shù)狀數(shù)組實(shí)現(xiàn)。

• 解法 1：樹(shù)狀數(shù)組 + 索引數(shù)組 $O(nlgn)$
• 解法 2：樹(shù)狀數(shù)組 + 最小堆 $O(nlgn)$

Q1.?K 個(gè)元素的最大和（Easy）

https://leetcode.cn/problems/maximum-sum-with-exactly-k-elements/

題目描述

給你一個(gè)下標(biāo)從?0?開(kāi)始的整數(shù)數(shù)組?nums?和一個(gè)整數(shù)?k?。你需要執(zhí)行以下操作?恰好?k?次，最大化你的得分：

1. 從?nums?中選擇一個(gè)元素?m?。
2. 將選中的元素?m?從數(shù)組中刪除。
3. 將新元素?m + 1?添加到數(shù)組中。
4. 你的得分增加?m?。

請(qǐng)你返回執(zhí)行以上操作恰好?k?次后的最大得分。

示例 1：

輸入：nums = [1,2,3,4,5], k = 3
輸出：18
解釋：我們需要從 nums 中恰好選擇 3 個(gè)元素并最大化得分。
第一次選擇 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 個(gè)元素并最大化得分。
第一次選擇 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

預(yù)備知識(shí) - 等差數(shù)列求和

• 等差數(shù)列求和公式：(首項(xiàng) + 尾項(xiàng)) * 項(xiàng)數(shù) / 2

題解（模擬 + 貪心）

顯然第一次操作的分?jǐn)?shù)會(huì)選擇數(shù)組中的最大值 max，后續(xù)操作是以 max 為首項(xiàng)的等差數(shù)列，直接使用等差數(shù)列求和公式即可。

class Solution {
    fun maximizeSum(nums: IntArray, k: Int): Int {
        val max = Arrays.stream(nums).max().getAsInt()
        return (max + max + k - 1) * k / 2
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(n)$ 其中 n 是 nums 數(shù)組的長(zhǎng)度；
• 空間復(fù)雜度：$O(1)$

Q2.?找到兩個(gè)數(shù)組的前綴公共數(shù)組（Medium）

https://leetcode.cn/problems/find-the-prefix-common-array-of-two-arrays/

題目描述

給你兩個(gè)下標(biāo)從?0?開(kāi)始長(zhǎng)度為?n?的整數(shù)排列?A?和?B?。

A?和?B?的?前綴公共數(shù)組?定義為數(shù)組?C?，其中?C[i]?是數(shù)組?A?和?B?到下標(biāo)為?i?之前公共元素的數(shù)目。

請(qǐng)你返回?A?和?B?的?前綴公共數(shù)組?。

如果一個(gè)長(zhǎng)度為?n?的數(shù)組包含?1?到?n?的元素恰好一次，我們稱這個(gè)數(shù)組是一個(gè)長(zhǎng)度為?n?的?排列?。

示例 1：

輸入：A = [1,3,2,4], B = [3,1,2,4]
輸出：[0,2,3,4]
解釋：i = 0：沒(méi)有公共元素，所以 C[0] = 0 。
i = 1：1 和 3 是兩個(gè)數(shù)組的前綴公共元素，所以 C[1] = 2 。
i = 2：1，2 和 3 是兩個(gè)數(shù)組的前綴公共元素，所以 C[2] = 3 。
i = 3：1，2，3 和 4 是兩個(gè)數(shù)組的前綴公共元素，所以 C[3] = 4 。

示例 2：

輸入：A = [2,3,1], B = [3,1,2]
輸出：[0,1,3]
解釋：i = 0：沒(méi)有公共元素，所以 C[0] = 0 。
i = 1：只有 3 是公共元素，所以 C[1] = 1 。
i = 2：1，2 和 3 是兩個(gè)數(shù)組的前綴公共元素，所以 C[2] = 3 。

提示：

• 1 <= A.length == B.length == n <= 50
• 1 <= A[i], B[i] <= n
• 題目保證?A?和?B?兩個(gè)數(shù)組都是?n?個(gè)元素的排列。

題解一（散列表）

從左到右遍歷數(shù)組，并使用散列表記錄訪問(wèn)過(guò)的元素，以及兩個(gè)數(shù)組交集：

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
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(n)$ 其中 n 是 nums 數(shù)組的長(zhǎng)度；
• 空間復(fù)雜度：$O(n)$ 散列表空間。

題解二（計(jì)數(shù)數(shù)組）

題解一需要使用多倍空間，我們發(fā)現(xiàn) A 和 B 都是 n 的排列，當(dāng)訪問(wèn)到的元素 nums[i] 出現(xiàn) 2 次時(shí)就必然處于數(shù)組交集中。因此，我們不需要使用散列表記錄訪問(wèn)過(guò)的元素，而只需要記錄每個(gè)元素出現(xiàn)的次數(shù)。

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
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(n)$ 其中 n 是 nums 數(shù)組的長(zhǎng)度；
• 空間復(fù)雜度：$O(n)$ 計(jì)數(shù)數(shù)組空間；

題解三（狀態(tài)壓縮）

既然 A 和 B 的元素值不超過(guò) 50，我們可以使用兩個(gè) Long 變量代替散列表優(yōu)化空間復(fù)雜度。

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
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(n)$ 其中 n 是 nums 數(shù)組的長(zhǎng)度；
• 空間復(fù)雜度：$O(1)$ 僅使用常量級(jí)別空間；

Q3.?網(wǎng)格圖中魚(yú)的最大數(shù)目（Hard）

https://leetcode.cn/problems/maximum-number-of-fish-in-a-grid/description/

題目描述

給你一個(gè)下標(biāo)從?0?開(kāi)始大小為?m x n?的二維整數(shù)數(shù)組?grid?，其中下標(biāo)在?(r, c)?處的整數(shù)表示：

• 如果?grid[r][c] = 0?，那么它是一塊?陸地?。
• 如果?grid[r][c] > 0?，那么它是一塊?水域?，且包含?grid[r][c]?條魚(yú)。

一位漁夫可以從任意?水域?格子?(r, c)?出發(fā)，然后執(zhí)行以下操作任意次：

• 捕撈格子?(r, c)?處所有的魚(yú)，或者
• 移動(dòng)到相鄰的?水域?格子。

請(qǐng)你返回漁夫最優(yōu)策略下，?最多?可以捕撈多少條魚(yú)。如果沒(méi)有水域格子，請(qǐng)你返回?0?。

格子?(r, c)?相鄰?的格子為?(r, c + 1)?，(r, c - 1)?，(r + 1, c)?和?(r - 1, c)?，前提是相鄰格子在網(wǎng)格圖內(nèi)。

示例 1：

輸入：grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]
輸出：7
解釋：漁夫可以從格子(1,3) 出發(fā)，捕撈 3 條魚(yú)，然后移動(dòng)到格子(2,3)?，捕撈 4 條魚(yú)。

示例 2：

輸入：grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]
輸出：1
解釋：漁夫可以從格子 (0,0) 或者 (3,3) ，捕撈 1 條魚(yú)。

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• 0 <= grid[i][j] <= 10

問(wèn)題抽象

求 “加權(quán)連通分量 / 島嶼問(wèn)題”，用二維 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
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(n · m)$ 其中 n 和 m 是 grid 數(shù)組的行和列；
• 空間復(fù)雜度：$O(n + m)$ 遞歸棧的最大深度。

題解二（并查集）

附贈(zèng)一份并查集的解法：

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

        // 父節(jié)點(diǎn)
        private val parent = IntArray(n * m) { it }
        // 高度
        private val rank = IntArray(n * m)
        // 數(shù)值
        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
        }
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(n · m)$ 其中 n 和 m 是 grid 數(shù)組的行和列；
• 空間復(fù)雜度：$O(n + m)$ 遞歸棧的最大深度。

相似題目：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-433413.html

• 130.?被圍繞的區(qū)域
• 200.?島嶼數(shù)量
• 990.?等式方程的可滿足性

推薦閱讀：

• 如何使用并查集解決朋友圈問(wèn)題？

Q4.?將數(shù)組清空（Hard）

https://leetcode.cn/problems/make-array-empty/

題目描述

給你一個(gè)包含若干?互不相同?整數(shù)的數(shù)組?nums?，你需要執(zhí)行以下操作?直到數(shù)組為空?：

• 如果數(shù)組中第一個(gè)元素是當(dāng)前數(shù)組中的?最小值?，則刪除它。
• 否則，將第一個(gè)元素移動(dòng)到數(shù)組的?末尾?。

請(qǐng)你返回需要多少個(gè)操作使?nums 為空。

示例 1：

輸入：nums = [3,4,-1]
輸出：5

示例 2：

輸入：nums = [1,2,4,3]
輸出：5

示例 3：

輸入：nums = [1,2,3]
輸出：3

提示：

• 1 <= nums.length <= 105
• 109?<= nums[i] <= 109
• nums?中的元素?互不相同?。

預(yù)備知識(shí) - 循環(huán)數(shù)組

循環(huán)數(shù)組：將數(shù)組尾部元素的后繼視為數(shù)組首部元素，數(shù)組首部元素的前驅(qū)視為數(shù)組尾部元素。

預(yù)備知識(shí) - 樹(shù)狀數(shù)組

OI · 樹(shù)狀數(shù)組

樹(shù)狀數(shù)組也叫二叉索引樹(shù)（Binary Indexed Tree），是一種支持 “單點(diǎn)修改” 和 “區(qū)間查詢” 的代碼量少的數(shù)據(jù)結(jié)構(gòu)。相比于線段樹(shù)來(lái)說(shuō)，樹(shù)狀數(shù)組的代碼量遠(yuǎn)遠(yuǎn)更少，是一種精妙的數(shù)據(jù)結(jié)構(gòu)。

樹(shù)狀數(shù)組核心思想是將數(shù)組 [0,x] 的前綴和拆分為不多于 logx 段非重疊的區(qū)間，在計(jì)算前綴和時(shí)只需要合并 logx 段區(qū)間信息，而不需要合并 n 個(gè)區(qū)間信息。同時(shí)，在更新單點(diǎn)值時(shí)，也僅需要修改 logx 段區(qū)間，而不需要（像前綴和數(shù)組）那樣修改 n 個(gè)信息?？梢哉f(shuō)，樹(shù)狀數(shù)組平衡了單點(diǎn)修改和區(qū)間和查詢的時(shí)間復(fù)雜度：

• 單點(diǎn)更新 add(index,val)：將序列第 index 位元素增加 val，時(shí)間復(fù)雜度為 O(lgn)，同時(shí)對(duì)應(yīng)于在邏輯樹(shù)形結(jié)構(gòu)上從小分塊節(jié)點(diǎn)移動(dòng)到大分塊節(jié)點(diǎn)的過(guò)程（修改元素會(huì)影響大分塊節(jié)點(diǎn)（子節(jié)點(diǎn)）的值）；
• 區(qū)間查詢 prefixSum(index)：查詢前 index 個(gè)元素的前綴和，時(shí)間復(fù)雜度為 O(lgn)，同時(shí)對(duì)應(yīng)于在邏輯樹(shù)形結(jié)構(gòu)上累加區(qū)間段的過(guò)程。

樹(shù)狀數(shù)組

問(wèn)題結(jié)構(gòu)化

1、概括問(wèn)題目標(biāo)

求消除數(shù)組的操作次數(shù)。

2、分析題目要件

• 觀察：在每次操作中，需要觀察數(shù)組首部元素是否為剩余元素中的最小值。例如序列 [3,2,1] 的首部元素不是最小值；
• 消除：在每次操作中，如果數(shù)組首部元素是最小值，則可以消除數(shù)組頭部元素。例序列 [1,2,3] 在一次操作后變?yōu)?[2,3]；
• 移動(dòng)：在每次操作中，如果數(shù)組首部元素不是最小值，則需要將其移動(dòng)到數(shù)組末尾。例如序列 [3,2,1] 在一次操作后變?yōu)?[2,1,3]。

3、觀察數(shù)據(jù)特征

• 數(shù)據(jù)量：測(cè)試用例的數(shù)據(jù)量上界為 10^5，這要求我們實(shí)現(xiàn)低于 O(n^2) 時(shí)間復(fù)雜度的算法才能通過(guò)；
• 數(shù)據(jù)大?。簻y(cè)試用例的數(shù)據(jù)上下界為 [-10^9, 10^9]，這要求我們考慮大數(shù)問(wèn)題。

4、觀察測(cè)試用例

以序列 [3,4,-1] 為例，一共操作 5 次：

• [3,4,-1]：-1 是最小值，將 3 和 4 移動(dòng)到末尾后才能消除 -1，一共操作 3 次；
• [3,4]：3 是最小值，消除 3 操作 1 次；
• [4]：4 是最小值，消除 4 操作 1 次；

5、提高抽象程度

• 序列：線性表是由多個(gè)元素組成的序列，除了數(shù)組的頭部和尾部元素之外，每個(gè)元素都有一個(gè)前驅(qū)元素和后繼元素。在將數(shù)組首部元素移動(dòng)到數(shù)組末尾時(shí)，將改變數(shù)組中的部分元素的關(guān)系，即原首部元素的前驅(qū)變?yōu)樵膊吭?，原尾部元素的后繼變?yōu)樵撞吭亍?/li>
• 是否為決策問(wèn)題：由于每次操作的行為是固定的，因此這道題只是純粹的模擬問(wèn)題，并不是決策問(wèn)題。

6、具體化解決手段

消除操作需要按照元素值從小到大的順序刪除，那么如何判斷數(shù)組首部元素是否為最小值？

• 手段 1（暴力枚舉）：枚舉數(shù)組剩余元素，判斷首部元素是否為最小值，單次判斷的時(shí)間復(fù)雜度是 O(n)；
• 手段 2（排序）：對(duì)原始數(shù)組做預(yù)處理排序，由于原始數(shù)組的元素順序信息在本問(wèn)題中是至關(guān)重要的，所以不能對(duì)原始數(shù)組做原地排序，需要借助輔助數(shù)據(jù)結(jié)構(gòu)，例如索引數(shù)組、最小堆，單次判斷的均攤時(shí)間復(fù)雜度是 O(1)。

如何表示元素的移動(dòng)操作：

• 手段 1（數(shù)組）：使用數(shù)組塊狀復(fù)制 Arrays.copy()，單次操作的時(shí)間復(fù)雜度是 O(n)；
• 手段 2（雙向鏈表）：將原始數(shù)組轉(zhuǎn)換為雙向鏈表，操作鏈表首尾元素的時(shí)間復(fù)雜度是 O(1)，但會(huì)消耗更多空間；

如何解決問(wèn)題：

• 手段 1（模擬）：模擬消除和移動(dòng)操作，直到數(shù)組為空。在最壞情況下（降序數(shù)組）需要操作 n^2 次，因此無(wú)論如何都是無(wú)法滿足題目的數(shù)據(jù)量要求；

至此，問(wèn)題陷入瓶頸。

解決方法是重復(fù)「分析問(wèn)題要件」-「具體化解決手段」的過(guò)程，枚舉掌握的算法、數(shù)據(jù)結(jié)構(gòu)和 Tricks 尋找突破口：

表示元素的移動(dòng)操作的新手段：

• 手段 3（循環(huán)數(shù)組）：將原數(shù)組視為循環(huán)數(shù)組，數(shù)組尾部元素的后繼是數(shù)組首部元素，數(shù)組首部元素的前驅(qū)是數(shù)組尾部元素，不再需要實(shí)際性的移動(dòng)操作。

解決問(wèn)題的新手段：

• 手段 2（計(jì)數(shù)）：觀察測(cè)試用例發(fā)現(xiàn)，消除每個(gè)元素的操作次數(shù)取決于該元素的前驅(qū)中未被消除的元素個(gè)數(shù)，例如序列 [3,4,-1] 中 -1 前有 2 個(gè)元素未被刪除，所以需要 2 次操作移動(dòng) 3 和 4，再增加一次操作消除 -1。那么，我們可以定義 rangeSum(i,j) 表示區(qū)間 [i,j] 中未被刪除的元素個(gè)數(shù)，每次消除操作只需要查詢上一次的消除位置（上一個(gè)最小值）與當(dāng)前的消除位置（當(dāng)前的最小值）中間有多少個(gè)數(shù)字未被消除 rangeSum(上一個(gè)最小值位置, 當(dāng)前的最小值位置)，這個(gè)區(qū)間和就是消除當(dāng)前元素需要的操作次數(shù)。

區(qū)分上次位置與當(dāng)前位置的前后關(guān)系，需要分類討論：

• id < preId：消除次數(shù) = rangeSum(id, preId)
• id > preId：消除次數(shù) = rangeSum(-1, id) + rangeSum(preId,n - 1)

如何實(shí)現(xiàn)手段 2（計(jì)數(shù)）：

在代碼實(shí)現(xiàn)上，涉及到「區(qū)間求和」和「單點(diǎn)更新」可以用線段數(shù)和樹(shù)狀數(shù)組實(shí)現(xiàn)。樹(shù)狀數(shù)組的代碼量遠(yuǎn)比線段樹(shù)少，所以我們選擇后者。

示意圖

答疑：

• 消除每個(gè)元素的操作次數(shù)不用考慮前驅(qū)元素中小于當(dāng)前元素的元素嗎？

由于消除是按照元素值從小到大的順序消除的，所以未被消除的元素一定比當(dāng)前元素大，所以我們不強(qiáng)調(diào)元素大小關(guān)系。

題解一（樹(shù)狀數(shù)組 + 索引數(shù)組）

• 使用「樹(shù)狀數(shù)組」的手段解決區(qū)間和查詢和單點(diǎn)更新問(wèn)題，注意樹(shù)狀數(shù)組是 base 1 的；
• 使用「索引數(shù)組」的手段解決排序 / 最小值問(wèn)題。

class Solution {
    fun countOperationsToEmptyArray(nums: IntArray): Long {
        val n = nums.size
        var ret = 0L
        // 索引數(shù)組
        val ids = Array<Int>(n) { it }
        // 排序
        Arrays.sort(ids) { i1, i2 ->
            // 考慮大數(shù)問(wèn)題
            // nums[i1] - nums[i2] x
            if (nums[i1] < nums[i2]) -1 else 1
        }
        // 樹(shù)狀數(shù)組
        val bst = BST(n)
        // 上一個(gè)被刪除的索引
        var preId = -1
        // 遍歷索引
        for (id in ids) {
            // 區(qū)間和
            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)}")
            }
            // 單點(diǎn)更新
            bst.dec(id)
            preId = id
        }
        return ret
    }

    // 樹(shù)狀數(shù)組
    private class BST(private val n: Int) {

        // base 1
        private val data = IntArray(n + 1)

        init {
            // O(nlgn) 建樹(shù)
            // for (i in 0 .. n) {
            //     update(i, 1)
            // }
            // O(n) 建樹(shù)
            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)
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(nlgn)$ 其中 n 是 nums 數(shù)組的長(zhǎng)度，排序 $O(nlgn)$、樹(shù)狀數(shù)組建樹(shù) $O(n)$、單次消除操作的區(qū)間和查詢和單點(diǎn)更新的時(shí)間為 $O(lgn)$；
• 空間復(fù)雜度：$O(n)$ 索引數(shù)組空間 + 樹(shù)狀數(shù)組空間。

題解二（樹(shù)狀數(shù)組 + 最小堆）

附贈(zèng)一份最小堆排序的代碼：

• 使用「樹(shù)狀數(shù)組」的手段解決區(qū)間和查詢和單點(diǎn)更新問(wèn)題，注意樹(shù)狀數(shù)組是 base 1 的；
• 使用「最小堆」的手段解決排序 / 最小值問(wèn)題。

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)
        }
        // 樹(shù)狀數(shù)組
        val bst = BST(n)
        // 上一個(gè)被刪除的索引
        var preId = -1
        // 遍歷索引
        while (!ids.isEmpty()) {
            val id = ids.poll()
            // 區(qū)間和
            if (id > preId) {
                ret += bst.rangeSum(preId, id)
            } else {
                ret += bst.rangeSum(-1, id) + bst.rangeSum(preId, n - 1)
            }
            // 單點(diǎn)更新
            bst.dec(id)
            preId = id
        }
        return ret
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(nlgn)$ 其中 n 是 nums 數(shù)組的長(zhǎng)度，堆排序 $O(nlgn)$、樹(shù)狀數(shù)組建樹(shù) $O(n)$、單次消除操作的區(qū)間和查詢和單點(diǎn)更新的時(shí)間為 $O(lgn)$；
• 空間復(fù)雜度：$O(n)$ 堆空間 + 樹(shù)狀數(shù)組空間。

相似題目：

• 315.?計(jì)算右側(cè)小于當(dāng)前元素的個(gè)數(shù)
• 1040.?移動(dòng)石子直到連續(xù) II

往期回顧

• LeetCode 單周賽第 342 場(chǎng) · 把問(wèn)題學(xué)復(fù)雜，再學(xué)簡(jiǎn)單
• LeetCode 單周賽第 341 場(chǎng)· 難度上來(lái)了，圖論的問(wèn)題好多??！
• LeetCode 雙周賽第 102 場(chǎng)· 這次又是最短路。
• LeetCode 雙周賽第 101 場(chǎng) · 是時(shí)候做出改變了！

到了這里，關(guān)于LeetCode 雙周賽 103（2023/04/29）區(qū)間求和的樹(shù)狀數(shù)組經(jīng)典應(yīng)用的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！