ZeroJudge 解題筆記：d194. 11572 - Unique Snowflakes

作者：王一哲
日期：2026年5月1日


ZeroJudge 題目連結：d194. 11572 - Unique Snowflakes

解題想法

用滑動視窗解題，用字典 $last$ 記錄每一個編號的雪花上次出現的索引值，視窗左端點為 $left$。接下來依序讀取目前的雪花編號為 $snow$、視窗右端點為 $right$，如果 $last$ 之中有 $snow$ 而且上一次出現的索引值大於等於 $left$，要更新視窗範圍，將 $left$ 改成 $last[snow] + 1$，再將 $last[snow]$ 更新為 $right$；最後更新最大值 $imax$，取 $imax$ 及 $right - left + 1$ 較大者。

Python 程式碼

使用時間約為 0.1 s，記憶體約為 24.7 MB，通過測試。

t = int(input())  # t 筆測資
for _ in range(t):  # 執行 t 次
    n = int(input())  # n 片雪花
    snowflake = [int(input()) for _ in range(n)]  # 讀取雪花編號
    last = dict()  # 每一個編號的雪花上次出現的索引值
    imax = 0  # 不同編號雪花數量最大值
    left = 0  # 滑動視窗左端點
    for right, snow in enumerate(snowflake):  # 依序讀取雪花編號
        if snow in last and last[snow] >= left:  # 如果 snow 在 last 之中，而且索引值大於等於左端點
            left = last[snow] + 1  # 更新左端點為目前雪花編號前一次出現的索引值加 1
        last[snow] = right  # 更新目前雪花編號出現的索引值為 right
        imax = max(imax, right - left + 1)  # 更新最大值
    print(imax)

使用時間約為 55 ms，記憶體約為 37.7 MB，通過測試。如果更新 $imax$ 時不呼叫 $max$，速度會更快，使用時間約為 45 ms，記憶體約為 34.9 MB，通過測試。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 1
    while ptr < len(data):
        n = int(data[ptr])  # n 片雪花
        ptr += 1
        last = dict()  # 每一個編號的雪花上次出現的索引值
        imax = 0  # 不同編號雪花數量最大值
        left = 0  # 滑動視窗左端點
        for right in range(n):  # 依序讀取雪花編號
            snow = data[ptr]
            ptr += 1
            if snow in last and last[snow] >= left:  # 如果 snow 在 last 之中，而且索引值大於等於左端點
                left = last[snow] + 1  # 更新左端點為目前雪花編號前一次出現的索引值加 1
            last[snow] = right  # 更新目前雪花編號出現的索引值為 right
            val = right - left + 1  # 更新最大值
            if val > imax: imax = val
            #imax = max(imax, right - left + 1)  
        result.append(f"{imax:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

使用時間約為 21 ms，記憶體約為 7.3 MB，通過測試。

#include <cstdio>
#include <unordered_map>
using namespace std;

int main() {
    int t; scanf("%d", &t);
    while(t--) {
        int n; scanf("%d", &n);
        unordered_map<int, int> last;
        int imax = 0, left = 0;
        for(int right=0; right<n; right++) {
            int snow; scanf("%d", &snow);
            if (last[snow] >= left) {
                left = last[snow] + 1;
            }
            last[snow] = right;
            int curr = right - left + 1;
            if (curr > imax) imax = curr;
        }
        printf("%d\n", imax);
    }
    return 0;
}