LeetCode 补充题 167. 各长度窗口公共元素的最大值
题目描述
给定长度为
n的整数数组nums。对于每个窗口长度k（1≤k≤n），考虑所有完整的长度为k的连续窗口，求同时出现在这些窗口中的最大整数；不存在时返回-1。返回长度为
n的数组answer，其中answer[k-1]对应窗口长度k。
示例 1：
输入：
nums = [1,3,2,5,3,1]
输出：[-1,-1,3,5,5,5]
解释： 长度 3 的所有窗口都有 3；长度至少 4 时，所有窗口都有 5。
示例 2：
输入：
nums = [2,2,2]
输出：[2,2,2]
解释： 每一种长度的每个窗口都含有 2。
提示：
-
1≤n≤10⁵，元素为32位有符号整数。 - 相同整数在一个窗口中出现一次即可，不要求每个窗口出现次数相等。
题意分析
目标不是分别计算每个窗口的最大值，而是找一个能在同长度所有窗口中出现的共同元素。对每个值先求“窗口至少多长才无法避开它”，再按长度汇总候选，可以避免逐长度逐窗口求交集。
这个最短窗口长度由该值出现位置之间的最大空白段决定；一旦某个长度满足要求，所有更长窗口也满足，因此最后可以用前缀最大值统一得到答案。
解法：按出现位置最大间隔归桶
核心思路
[!blue]
换一个问题问：对固定值
x，窗口至少多长，才能保证每个窗口都碰到一次x？这取决于最长的“不含 x”的空白段，不需要逐个维护窗口最大值。将
x的出现位置两端补上-1和n。相邻位置相差d时，中间恰有d - 1个位置不含x；取所有间隔的最大值后，长度小于d的窗口可以完全落进空白段，长度至少为d的窗口则无法避开x。代码中
stats[x][0]保存最近位置，stats[x][1]保存目前最大间隔；扫描结束再补上末尾间隔。bucket[d]记录从长度d开始符合条件的最大值，之后求前缀最大值，就得到每种窗口长度的答案。has、found单独表示是否存在候选，不能让初始的 0 压过合法负数。例如长度为 5 的数组中，
x出现在下标1、4，补边界后位置为-1、1、4、5，最大间隔为 3：长度为 2 的窗口可能落在下标2、3，长度达到 3 后就无法完全避开x。
解题步骤
- 为每个值记录上次位置和最大相邻出现间隔，边界补 -1 与 n。
- 最大间隔 d 表示该值从窗口长度 d 起必在每个窗口中出现，将其放入桶 d。
- 对桶求前缀最大值，使用独立存在标记兼容负数。
代码实现
class Solution {
public int[] sharedMax(int[] nums) {
int n = nums.length;
Map<Integer, int[]> stats = new HashMap<>();
for (int i = 0; i < n; i++) {
int[] s = stats.computeIfAbsent(nums[i], x -> new int[] {
-1,
0
});
s[1] = Math.max(s[1], i - s[0]);
s[0] = i;
}
int[] bucket = new int[n + 1];
int[] out = new int[n];
boolean[] has = new boolean[n + 1];
for (Map.Entry<Integer, int[]> e : stats.entrySet()) {
int[] s = e.getValue();
int d = Math.max(s[1], n - s[0]);
if (!has[d] || e.getKey() > bucket[d]) {
bucket[d] = e.getKey();
}
has[d] = true;
}
boolean found = false;
int best = 0;
for (int k = 1; k <= n; k++) {
if (has[k]) {
if (!found || bucket[k] > best) {
best = bucket[k];
}
found = true;
}
out[k - 1] = found ? best : -1;
}
return out;
}
}
func sharedMax(nums []int) []int {
n := len(nums)
stats := map[int][2]int{}
for i, x := range nums {
s, ok := stats[x]
if !ok {
s[0] = -1
}
s[1] = max(s[1], i-s[0])
s[0] = i
stats[x] = s
}
bucket := make([]int, n+1)
has := make([]bool, n+1)
for x, s := range stats {
d := max(s[1], n-s[0])
if !has[d] || x > bucket[d] {
bucket[d] = x
}
has[d] = true
}
out := make([]int, n)
found, best := false, 0
for k := 1; k <= n; k++ {
if has[k] {
if !found || bucket[k] > best {
best = bucket[k]
}
found = true
}
out[k-1] = -1
if found {
out[k-1] = best
}
}
return out
}
复杂度分析
- 时间复杂度：使用哈希表，期望时间 $O(n)$。
- 空间复杂度：$O(n)$。
关键点总结
[!green]
两个出现位置之间最长缺失段长为 d-1，所以每个 k 窗口都含该值当且仅当 k>=d。
易错点总结
[!yellow]
不是求每个窗口各自的最大值，而是先取全部窗口的元素交集，再取最大值。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 828. 统计子串中的唯一字符 | 困难 | 都按相同元素的相邻出现位置界定窗口边界；本题用最大空隙推导能覆盖每个窗口的最小长度，该题用前后位置统计恰好出现一次的区间贡献。 |