d194 - 11572 - Unique Snowflakes

🔗 前往 ZeroJudge 原題

題目描述

題目要求找出在給定雪花序列中，可以找到的最大相異雪花數量。可以將雪花序列視為一個流，可以隨時停止打包，但一旦開始打包，必須將當前的雪花加入盒子，直到盒子滿為止。目標是找到最大盒子大小，使得盒子中的所有雪花都不同。

解題思路

這題可以使用 sliding window 的概念，搭配 hash table (map) 來解決。map 用於記錄每個雪花最後出現的位置。 迭代雪花序列，對於每個雪花，檢查它是否已經在 map 中存在。如果存在，則更新 map 中該雪花的出現位置。 計算當前視窗的大小 (即當前雪花的索引減去該雪花最後一次出現的位置)。 更新最大視窗大小。

複雜度分析

• 時間複雜度: O(n)，其中 n 是雪花序列的長度。因為我們迭代序列一次，並且 map 的查找和更新操作平均時間複雜度為 O(1)。
• 空間複雜度: O(n)，在最壞情況下，所有雪花都不同，map 需要存儲所有雪花。

程式碼

#include <iostream>
#include <map>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	int t,n,x;
	cin >> t;
	while(t--){
		cin >> n;
		int ans=0,mi=0;
		map <int,int> mp;
		for(int i=1;i<=n;++i){
			cin >> x;
			mi=max(mi,mp[x]);
			mp[x]=i;
			ans=max(i-mi,ans);
		}
		cout << ans << "\n";
	}
}