【例61.2】 最近的一对

解题思路

用map存每个值最近一次出现下标。当前j与该值最近位置i组成最近候选，比较j-i；更短更新，相等则选更小i。

正确性说明

对固定右端j，最短同值配对必是前一次出现；更早同值只会更远。所有全局最短候选都在这些相邻出现对中，逐个比较即可得到最优及平局规则。

易错点

不能只保存首次出现位置；题目平局按前端下标而不是数值。

复杂度

时间O(n log n)，空间O(n)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    map<long long, int> last;
    int best = INT_MAX, left = INT_MAX;
    long long ans = 0;
    for (int j = 1; j <= n; j++) {
        long long x;
        cin >> x;
        auto it = last.find(x);
        if (it != last.end()) {
            int i = it->second, d = j - i;
            if (d < best || (d == best && i < left)) {
                best = d;
                left = i;
                ans = x;
            }
        }
        last[x] = j;
    }
    if (best == INT_MAX)
        cout << "No\n";
    else
        cout << ans << "\n";
    return 0;
}