P3208. 最小矩阵宽度

解题思路

贪心地选满列向

本题只需要找到最小宽度的子矩阵，对高度不做要求。

举个例子，对于题目所给示例：

选择子矩阵：

和

在只考虑宽度的限定条件下，它们的宽度均为 3。

贪心地思考这个问题，我们在每次选择时必然会把列向的整个高度都选择上，这样找到的子矩阵的宽度才能够尽可能地小。

因此问题就转变为了，在行向选择若干连续的列，使得构成的子矩阵能够覆盖给定的长度为 K 的数组。这显然就是一个借助哈希表来辅助的滑窗问题。

列向数据预处理

我们可以先把每一列“拍扁”，用一个二维列表 col_contain_lst 统计每一列所包含的元素。

col_contain_lst[i] 是一个计数器哈希表，记录了第 i 列所包含的元素以及个数。

其构建过程如下：

滑窗三问三答

构建一个新的哈希表 win_cnt，用于储存窗口中的元素以及其个数。此外还需要另一个哈希表 cnt，用于储存长度为 K 的目标数组的元素以及个数。

滑窗三问

Q1：对于每一个右指针 right 所指的列 col，做什么操作？

Q2：什么时候要令左指针 left 右移？left 对应的列 col_left 做什么操作？while 中的循环不变量是什么？

Q3：什么时候进行 ans 的更新？

滑窗三答

A1：将第 right 列各个元素出现的个数，加入到用于储存窗口中的元素以及其个数的哈希表 win_cnt 中。

A2：哈希表 cnt 的每一个元素均在 win_cnt 中出现，且个数小于等于窗口中的元素个数。可以新建一个 check() 函数来表示这个过程：

left 不断右移，直到该条件不满足。

A3：当 check() 满足时，可以更新答案。

复杂度分析 设矩阵为 n 行 m 列，目标数组长度为 k。预处理阶段把每一列拍扁成一个计数哈希表 col_contains_lst[j]，需要访问矩阵中每个元素恰好一次，时间 O(n·m)。滑窗阶段，right 从第 0 列扫到第 m-1 列，left 只单调右移，每一列至多整体进窗一次、出窗一次；一列进窗或出窗时要合并或回退该列计数表中的键值对，每列至多 n 个键，合计仍是 O(n·m)。check 函数每次要比较目标哈希表 cnt 的全部键，单次代价 O(k)；它在每次 right 右移后以及 left 每次右移前各调用一次，调用总次数不超过 2m 量级，合计 O(m·k)。因此总时间复杂度为 O(n·m + m·k)。空间上，所有列计数表合计至多存 n·m 个键值对，加上目标计数表和窗口计数表的 O(k) 与 O(n·m)，空间复杂度为 O(n·m + k)。