CSES – Playlist

題目連結

題意

給 N 首歌曲，問最長歌曲都不一樣的區間長度。

解題想法

這題我們用雙指標的想法來做，每次我們都維護一個合法 (每個歌曲都不一樣) 的區間。
用 map 來判斷每個曲子出現的次數。如果出現一次以上的話，就移動區間的左界直到剩下每個歌曲剩下一種。
我們並不用每次都要重新跑過區間算次數。因為只有新加入歌曲的時候才會造成有大於一次的情況。
只需要在每次遇到大於一的時候，將左界持續移動直到 mp[a[r]] == 0 就可以繼續移動右界。

時間複雜度: O(nlogn)

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector <int> a(n+1);
    a[n] = -1;
    for(int i = 0;i < n;i++) cin >> a[i];
    int l = 0, r = 0;
    int ans = 0;
    map <int,int> mp;
    while(r < n){
        while(mp[a[r]] == 0 && r < n){ // 只要出現 > 1 次就不會移動右界
            mp[a[r]]++; 
            r++;
        }
        ans = max(ans, (r-l));
        mp[a[l]]--;
        l++;
    }
    cout << ans << '\n';
}