K 個元素的最大和

【貪心】反復(fù)用最大值，等差數(shù)列求和。

找到兩個數(shù)組的前綴公共數(shù)組

【哈希集合】用兩個set求交集。

【位運算優(yōu)化】用位運算表示集合，兩個數(shù)的AND表示集合的交集，交集的大小就是二進制中1的個數(shù)。

網(wǎng)格圖中魚的最大數(shù)目

【DFS】DFS求出每個非0連通塊元素和的最大值，最大值即為答案。

【BFS】BFS求出每個非0連通塊元素和的最大值，最大值即為答案。

將數(shù)組清空

【二分 + 離散化】通過構(gòu)建映射和有序列表，計算間隔和操作數(shù)，實現(xiàn)對列表元素的快速刪除、移動和獲取。遍歷?nums?的前?n-1?個元素，記錄每個元素與下一個元素之間的間隔?interval?和需要移動這兩個元素到末尾的操作數(shù)。在記錄操作數(shù)時，根據(jù)?i?和?j?的大小關(guān)系來選擇字符串?'i < j'?或?'i >= j'。如果?i > j，表示需要先移除后面最小的元素，因此操作數(shù)加上?n - x（x?表示當(dāng)前元素在?nums?中的位置）

【樹狀數(shù)組】因為只有當(dāng)前最小值才會被標(biāo)記，因此指針肯定是先標(biāo)記數(shù)組最小值，再標(biāo)記次小值，因此我們先把所有下標(biāo)i按nums[i]從小到大排序，就得到了指針的標(biāo)記順序。接下來只要研究指針標(biāo)記i之后到標(biāo)記j的時候需要進行幾次操作即可。由于每一次操作會將指針指向下一個未被標(biāo)記的數(shù)，因此操作的數(shù)量即為“下標(biāo)1和j之間，未被標(biāo)記的數(shù)的個數(shù)”。使用樹狀數(shù)組就能在每次O(Iogn)的復(fù)雜度內(nèi)完成查詢和維護，因此總體復(fù)雜度為O(n log n)。

【思維】在統(tǒng)計移動次數(shù)時，遇到要刪除的元素，相當(dāng)于可以免費向后移動一步（因為刪除操作已經(jīng)計入答案）。試想一下，如果數(shù)組是單調(diào)遞增的，就沒有任何額外的移動次數(shù)。如果第k次要刪除的元素在第k一1次要刪除的元素的左側(cè)，那么必須多走一整圈，移動次數(shù)為-k。累加，即為總的移動次數(shù)。