洛谷：P1638：逛画展

题目

P1638：逛画展

分析

这是一道深入理解“双指针”的习题。

先看样本数据：

12 5
2 5 3 1 3 2 4 1 1 5 4 3

而答案是2 7，表示从第二幅看到第七幅（5 3 1 3 2 4），能看到所有画家（1-5），且花费最少。

这样的一个区间有什么特性？

首先，必须所有的画家都出现至少一次；其次，不能缩减，也就是说，左边界不能往右，右边界也不能再往左——这是一个很强烈、很明确的“双指针”解题。

解题思路如下：

1. 首先从第一个开始，不断扩展右边界，直到包含了所有的画家为止。
2. 然后不断右移左边界，剔除可能重复的画家，但不能出现少了一个画家为止。

核心代码是：

while (unique == m) {
    // 如果找到更小的窗口，更新记录
    if (right - left + 1 < min_len) 
    {
      min_len = right - left + 1;
      result_left = left;
      result_right = right;
    }

    // 移动左边界，减少左边画家的计数
    count[a
]--;

    // 如果某个画家的计数减到0，减少unique计数
    if (count[a
] == 0) 
    {
      unique--;
    }

    left++;
}

答案

思考

这个双指针解法很优雅，时间复杂度是\(O(N)\)，非常高效。