利用 Stack 上的陣列空間來加速執行速度

今天練習的題目是 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% 的結果。