✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题（建议用时：90分钟/套）
• 对照解析查漏补缺
• 配套练习题库

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

春秋招合集 -> 互联网必备刷题宝典🔗

题目一：寻找凸包之外的最小数

1️⃣：维护前缀的最小值和最大值

2️⃣：根据最小值判断答案：最小值大于0则答案为0，否则答案为最大值+1

难度：中等

这道题目的关键在于理解"数值区间凸包"的概念，并发现答案只有两种可能：要么是0（当区间内最小值大于0时），要么是区间内最大值加1（当区间内最小值等于0时）。通过维护前缀的最小值和最大值，我们可以在O(n)时间内求解这个问题。

题目二：循环矩阵中的零区域最大面积

1️⃣：分析循环矩阵的特性，将问题转化为原字符串上的连续0子串问题

2️⃣：计算原字符串中最长连续0的长度（考虑环形）

3️⃣：通过数学推导，得出最大面积为三角形面积公式L(L+1)/2

难度：中等偏难

这道题目需要理解循环矩阵的性质，发现在矩阵中选取的区域对应原字符串上的连续子串。通过数学推导，我们可以证明最优解是一个直角三角形，并给出面积计算公式，实现O(n)的高效解法。

题目三：乘积查询器

1️⃣：建立数值到位置的映射表，记录每个数字出现的所有位置

2️⃣：对于每个查询x，枚举其所有因数对

3️⃣：检查因数对是否在数组中，并处理特殊情况

难度：中等

这道题目考察了高效查询技巧和数学知识。通过预处理数组元素的位置信息，结合枚举因数对的方法，我们可以在O(n + q*sqrt(x))的时间复杂度内解决问题，避免了暴力枚举所有元素对的高复杂度。

01. 寻找凸包之外的最小数

问题描述

小柯最近在研究数据序列分析，她定义了一个概念叫"数值区间凸包"。对于一个数组 的区间 ，该区间的"数值区间凸包"定义为 。

现在，小柯想要进行一系列分析，对于数组的每个前缀 （ 从 到 ），她需要找出不在这个前缀的"数值区间凸包"内的最小非负整数。换句话说，对于前缀 ，如果其"数值区间凸包"是 ，她需要找出区间 中不在 内的最小整数。

输入格式

第一行输入一个整数 （），表示数组的长度。

第二行输入 个整数 （），表示数组的元素。

输出格式

输出一行 个整数，第 个整数表示数组前缀 的"数值区间凸包"外的最小非负整数。

样例输入

5
1 0 4 5 1

样例输出

0 2 5 6 6

数据范围

题解

这道题目看起来有点绕，但本质上非常直观。对于数组的每个前缀 ，我们需要找出不在"数值区间凸包" 内的最小非负整数。

我们可以分析一下：

1. 如果前缀中的最小值 ，那么最小的不在凸包内的非负整数一定是
2. 如果前缀中的最小值 ，那么区间 内的所有整数都在凸包内，所以答案是

实现上，我们只需要维护前缀的最小值 和最大值 ，然后根据上述规则判断即可。

时间复杂度分析：我们只需要遍历一次数组，并在每一步更新最小值和最大值，所以时间复杂度是 ，空间复杂度是 （存储结果）。

对于样例输入：

5
1 0 4 5 1

处理过程如下：

1. 前缀[1,1]：，答案为0
2. 前缀[1,2]：，答案为2
3. 前缀[1,3]：，答案为5
4. 前缀[1,4]：，答案为6
5. 前缀[1,5]：，答案为6

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

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

# 初始化最小值和最大值
minv = float('inf')
maxv = -1
res = []

# 遍历数组，维护前缀的最小值和最大值
for x in nums:
    # 更新前缀的最小值和最大值
    minv = min(minv, x)
    maxv = max(maxv, x)
    
    # 判断答案：如果前缀最小值大于0，答案为0；否则答案为maxv+1
    if minv > 0:
        res.append(0)
    else:
        res.append(maxv + 1)

# 输出结果
print(" ".join(map(str, res)))

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    // 初始化前缀最值
    int mn = 1e9 + 1, mx = -1;
    vector<int> ans(n);
    
    // 遍历更新前缀最值并计算答案
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        mn = min(mn, x);  // 更新最小值
        mx = max(mx, x);  // 更新最大值
        
        // 如果最小值大于0，答案为0；否则答案为最大值+1
        if (mn > 0)
            ans[i] = 0;
        else
            ans[i] = mx + 1;
    }
    
    // 输出结果
    for (int i = 0; i < n; i++)
        cout << ans[i] << (i == n-1 ? "\n" : " ");
    
    return 0;
}

• Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] strArr = br.readLine().trim().split(" ");
        
        // 初始化前缀最值
        int mnVal = Integer.MAX_VALUE;
        int mxVal = -1;
        StringBuilder sb = new StringBuilder();
        
        // 遍历数组
        for (int i = 0; i < n; i++) {
            int cur = Integer.parseInt(strArr[i]);
            mnVal = Math.min(mnVal, cur);  // 更新最小值
            mxVal = Math.max(mxVal, cur);  // 更新最大值
            
            // 计算答案
            if (mnVal > 0) {
                sb.append(0);
            } else {
                sb.append(mxVal + 1);
            }
            
            if (i < n - 1) {
                sb.append(" ");
            }
        }
        
        System.out.println(sb.toString());
    }
}

02. 循环矩阵中的零区域最大面积

问题描述

小基是一位图像处理专家，他在研究一种特殊的图像模式。给定一个由0和1组成的字符串 ，他需要构建一个特殊的方形矩阵。这个矩阵的第一行就是原始字符串 ，第二行是 向右循环移动一位的结果，第三行是 向右循环移动两位的结果，以此类推，直到构成一个 的方形矩阵（其中 是字符串 的长度）。

在这个矩阵中，小基想要找出由0组成的最大区域面积。一个区域可以是矩形或者直角三角形（其直角边分别平行于矩阵的行和列）。

输入格式

输入一个长度为 的二进制字符串 ，仅包含字符0和1，其中 。

输出格式

输出一个整数，表示矩阵中由0组成的最大区域面积。

样例输入

00110

样例输出

6

数据范围

• 
• 字符串 仅包含字符'0'和'1'

题解

这道题目乍看起来可能需要构建整个矩阵，然后搜索所有可能的矩形和三角形区域。但通过仔细分析，我们可以发现一些数学规律，从而大大简化解法。

首先，我们来分析一下这个循环移位构建的矩阵有什么特性：

• 对于矩阵中的任何一个坐标 ，其值实际上是原字符串中的

这个特性意味着，当我们在矩阵中选取一个矩形或直角三角形区域时，它对应到原字符串上，就是一段连续的（可能环形的）子串。

基于这个性质，我们可以推导出：

1. 如果字符串 全为0，那么整个矩阵都是0，最大面积就是
2. 如果字符串中存在1，我们需要找出 中最长的连续0子串（考虑环形），设其长度为
3. 对于长度为 的连续0子串，能构成的最大区域面积是 （一个直角三角形）

为什么是三角形而不是矩形？因为当我们尝试构建一个高度为 、宽度为 的矩形时，必须满足 ，这个约束下，当 或者 时面积最大为 。

但如果构建一个直角三角形，底边长度为 ，高度也为 ，其面积为 ，这比矩形的面积更大。实际上，对于长度为 的连续0子串，最优的形状是一个"阶梯状"的直角三角形，其面积为 。

因此，我们的算法很简单：

1. 统计字符串 中最长的连续0子串长度 （需考虑环形，即首尾相连的情况）
2. 如果 （即 全为0），答案为
3. 否则，答案为

时间复杂度为O(n)，空间复杂度为O(n)（考虑到需要构造s+s来处理环形情况）。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入
s = input()
n = len(s)

# 计算最长连续0序列（考虑环形）
s2 = s + s  # 将字符串复制一遍处理环形情况
max_len = 0
curr = 0

# 遍历统计连续0的最大长度
for ch in s2:
    if ch == '0':
        curr += 1
        max_len = max(max_len, curr)
    else:
        curr = 0
        
# 限制最大长度不超过n
max_len = min(max_len, n)

# 计算答案
if max_len == n:  # 字符串全为0
    ans = n * n
else:  # 连续0的最大长度为max_len
    ans = (max_len * (max_len + 1)) // 2
    
print(ans)