题解

题面描述

给定一个整数 $n$ 和一个长度为 $n$ 的数组 $a_1,a_2,\dots,a_n$。定义任意区间 $[l,r]$ 的数字凸包区间为

对于每个前缀 $[1,i]$（$i=1,2,\dots,n$），求该前缀构成的数字凸包区间中不属于该区间的最小非负整数。

例如：

• 当 $i=1$ 时，区间为 $[\min\{a_1\},\max\{a_1\}]=[a_1,a_1]$，如果 $a_1\neq 0$ 则 $0$ 不在该区间，答案为 $0$；
• 当 $i\ge 1$ 且 $\min\{a_1,\dots,a_i\}=0$ 时，则区间为 $[0,M]$（其中 $M=\max\{a_1,\dots,a_i\}$），区间内包含所有 $0,1,\dots,M$，所以答案为 $M+1$。

思路分析

对于每个 $i$，我们只需维护前缀的最小值 $m_i$ 和最大值 $M_i$。

• 若 $m_i>0$，说明区间 $[m_i,M_i]$ 不包含 $0$，因此答案为 $0$。
• 若 $m_i=0$，则区间为 $[0,M_i]$，因此答案为 $M_i+1$。

时间复杂度为 $O(n)$，适用于 $n\le 2\times 10^5$ 的数据规模。

代码分析

在遍历数组时维护两个变量：

• min_val：前缀最小值
• max_val：前缀最大值

对于每个位置 $i$：

1. 更新 $min\_val = \min(min\_val, a_i)$
2. 更新 $max\_val = \max(max\_val, a_i)$
3. 如果 $min\_val>0$，输出答案 $0$；否则输出答案 $max\_val+1$。

C++

#include <iostream>
#include <algorithm>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    int a;
    // 初始化前缀最小值为一个较大的数，前缀最大值为0
    int min_val = 1e9 + 1, max_val = 0;
    for (int i = 1; i <= n; i++){
        cin >> a;
        // 更新前缀最小值和最大值
        min_val = min(min_val, a);
        max_val = max(max_val, a);
        // 如果前缀中最小值大于0，则答案为0；否则答案为 max_val+1
        if(min_val > 0)
            cout << 0 << " ";
        else
            cout << max_val + 1 << " ";
    }
    return 0;
}

Python

# 读取输入
n = int(input())
a_list = list(map(int, input().split()))

# 初始化前缀最小值为较大的数，前缀最大值为0
min_val = 10**9 + 1
max_val = 0
result = []

# 遍历数组更新前缀最值
for i in range(n):
    a = a_list[i]
    min_val = min(min_val, a)  # 更新前缀最小值
    max_val = max(max_val, a)  # 更新前缀最大值
    # 判断前缀最小值是否大于0
    if min_val > 0:
        result.append(0)
    else:
        result.append(max_val + 1)
        
# 输出结果，以空格分隔
print(" ".join(map(str, result)))

Java

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        // 使用BufferedReader提高输入效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] parts = br.readLine().trim().split("\\s+");
 
        // 初始化前缀最小值和前缀最大值
        int minVal = (int)1e9 + 1;
        int maxVal = 0;
        StringBuilder sb = new StringBuilder();
 
        // 遍历数组更新前缀最值
        for (int i = 0; i < n; i++) {
            int a = Integer.parseInt(parts[i]);
            // 更新前缀最小值
            minVal = Math.min(minVal, a);
            // 更新前缀最大值
            maxVal = Math.max(maxVal, a);
            // 如果前缀最小值大于0，则输出0；否则输出 maxVal+1
            if (minVal > 0) {
                sb.append("0 ");
            } else {
                sb.append((maxVal + 1) + " ");
            }
        }
 
        // 输出结果
        System.out.println(sb.toString().trim());
    }
}

题目内容

米小游有$n$个整数{$a_1,a_2,...,a_n$}，他定义区间$[l,r]$的“数字凸包区间”为 [$min${$a_l,...,a_r$},$max${$a_l,...,a_r$}]。

现在，对于每一个$i= 1,2,...,n$，直接输出不属于$[1,i]$这个区间的“数字凸包区间”的最小非负整数。

输入描述

第一行输入两个整数$n(1≦n≦2×10^5)$代表整数数量询问次数。

第二行输入$n$个整数$a_1,a_2,...,a_n(0≦a_i≦10^9)$代表元素

输出描述

在一行上输出$n$个整数，代表对于每一个$i$的答案。

样例1

输入

5
1 0 4 5 1

输出

0 2 5 6 6

说明

对于第一次询问，“数字凸包区间”为$[1,1]$，不属于这个“数字凸包区间”的最小非负整数为$0$。

对于第二次询问，“数字凸包区间”为$[0,1]$，不属于这个“数字凸包区间”的最小非负整数为$2$。