今天練習的題目是 3186. Maximum Total Damage With Spell Casting，我使用的方法是先對輸入陣列排序，然後再使用 stack 上固定大小的陣列來處理輸入陣列的資料，因為題目有對輸入陣列數量限制在 $10^5$ 以內，這樣的做法對靜態編譯的程式語言，通常都可以跑出不錯的執行時間。
C++ 就用 array< int, 100000> arr 來加速。
class Solution {
public:
long long maximumTotalDamage(vector< int>& power) {
int n = 0;
array< int, 100000> arr;
array< int, 100000> count;
ranges::sort(power);
for (auto p : power) {
if (n == 0 || arr[n - 1] != p) {
++n;
arr[n - 1] = p;
count[n - 1] = 1;
} else {
count[n - 1]++;
}
}
vector< long long> f(n, 0);
long long mx = 0;
for (int i = 0, j = 0; i < n; ++i) {
while (i > j && arr[i] > arr[j] + 2) {
mx = max(mx, f[j]);
++j;
}
f[i] = mx + 1LL * arr[i] * count[i];
}
return *ranges::max_element(f);
}
};
Python3 比較特別，還是直接用 Counter 比較快，因為它有特別的最佳化處理，對於動態編譯執行的程式語言，還是多利用最佳化的內建函式，才會比較有效率。
class Solution:
def maximumTotalDamage(self, power: List[int]) -> int:
freq = Counter(sorted(power))
keys = list(freq.keys())
values = list(freq.values())
n = len(keys)
f = [0] * n
j = 0
mx = 0
for i in range(n):
while i > j and keys[i] > keys[j] + 2:
mx = max(mx, f[j])
j += 1
f[i] = mx + keys[i] * values[i]
return max(f)
Go 就用 arr := [100000]int{} 來加速。
func maximumTotalDamage(power []int) int64 {
n := 0
slices.Sort(power)
arr := [100000]int{}
count := [100000]int{}
for _, p := range power {
if n == 0 || arr[n-1] != p {
n += 1
arr[n-1] = p
count[n-1] = 1
} else {
count[n-1]++
}
}
j := 0
var mx int64
f := make([]int64, n)
for i := range n {
for i > j && arr[i] > arr[j]+2 {
mx = max(mx, f[j])
j++
}
f[i] = mx + int64(arr[i])*int64(count[i])
}
return slices.Max(f)
}
Rust 就用 let mut arr = [0; 100000] 來加速。
impl Solution {
pub fn maximum_total_damage(mut power: Vec<i32>) -> i64 {
power.sort_unstable();
let mut arr = [0; 100000];
let mut count = [0; 100000];
let mut n = 0;
for p in power {
if n == 0 || arr[n - 1] != p as usize {
n += 1;
arr[n - 1] = p as usize;
count[n - 1] = 1;
} else {
count[n - 1] += 1;
}
}
let mut f = vec![0i64; n];
let mut j = 0;
let mut mx = 0;
for i in 0..n {
while i > j && arr[i] > arr[j] + 2 {
mx = mx.max(f[j]);
j += 1;
}
f[i] = mx + arr[i] as i64 * count[i] as i64;
}
f.into_iter().max().unwrap()
}
}
在 LeetCode 上面看到 C++/Python3 排名前面都有用 display_runtime.txt 作弊，如果是用這個方法加上 display_runtime.txt 作弊可以輕鬆跑出 Runtime 0ms Beats 100% 的結果。
