题目
小郑的整除版子序列
解题思路（只关心模 M 的余数）
问题本质：子序列 vs 子数组
题目要求判断是否存在一个子序列（不要求连续，但保持原顺序），其元素之和能被给定的正整数 M 整除。
关键误区在于：子序列 ≠ 连续子数组。例如在数组 [1, 2, 3, 3] 中，选择第 1、3、4 个元素得到 1 + 3 + 3 = 7，虽然不连续，但合法。因此，依赖前缀和与同余的经典“子数组”方法在此失效。
核心观察：只关心模 M 的余数
由于我们只关心和是否能被 M 整除，即和 \bmod M = 0，因此无需记录具体和的大小，只需跟踪所有可能的余数。
因为模 M 的结果只有 0, 1, 2, \dots, M-1 共 M 种可能，而题目保证 M < 100，状态空间极小，适合动态维护。
我们不需要知道具体的和是多少，只需要知道“是否能得到余数 0”。
动态维护可行余数集合
我们用一个集合 possible 动态记录：当前已处理的元素中，通过选择任意非空子序列所能得到的所有余数（对 M 取模）。
- 初始时，
possible为空（尚未选择任何元素）。 - 对每个新元素 a_i：
- 它可以单独作为一个子序列，贡献余数 r = a_i \bmod M；
- 也可以附加到之前所有已知子序列之后，将每个已有余数 s 更新为 (s + r) \bmod M。
- 每次更新后，检查
0是否出现在集合中。若出现，说明存在非空子序列和能被 M 整除，立即返回YES。
举例说明过程
以输入 N=4, M=7, a=[1, 2, 3, 3] 为例：
-
处理
1：余数 =1 % 7 = 1所以possible = {1} -
处理
2：现在有两种选择：-
不选它 → 保留之前的
{1} -
选它：
- 单独选 2 → 余数 2
- 或者在之前的基础上加 2：
1 + 2 = 3→ 余数 3
→
possible = {1, 2, 3} -
-
处理
3：- 单独选 3 → 余数 3（已有）
- 在已有基础上加 3：
1+3=42+3=53+3=6→possible = {1,2,3,4,5,6}
-
处理
3：- 单独选 3 → 3（已有）
- 在已有基础上加 3：
1+3=4（已有）2+3=5（已有）3+3=6（已有）4+3=7 → 7 % 7 = 0→ ✅ 得到余数 0！
一旦发现 0 出现在 possible 中，就立刻输出 YES 并结束！
该过程覆盖了所有非空子序列的组合，且因状态压缩（仅存余数），效率极高。
参考代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int[] a = new int[N];
for (int i = 0; i < N; i++) {
a[i] = sc.nextInt();
}
// possible 集合：存储所有非空子序列的和对 M 取模后的余数
Set<Integer> possible = new HashSet<>();
for (int i = 0; i < N; i++) {
// 计算当前元素对 M 的余数
int r = a[i] % M;
// 创建新集合，初始包含“不选当前元素”的所有旧余数
Set<Integer> newPossible = new HashSet<>(possible);
// 情况1：单独选择当前元素，形成长度为1的子序列
newPossible.add(r);
// 情况2：将当前元素附加到每一个已有的子序列末尾
for (int sum : possible) {
int newRemainder = (sum + r) % M;
newPossible.add(newRemainder);
}
// 更新 possible 为包含当前元素后的新状态
possible = newPossible;
// 若已能构造出余数为0的非空子序列，直接输出 YES 并退出
if (possible.contains(0)) {
System.out.println("YES");
return;
}
}
// 遍历完所有元素仍未找到余数0，说明不存在满足条件的非空子序列
System.out.println("NO");
}
}
最大区间
解题思路（单调栈优化枚举）
问题本质：最大化“长度 × 区间最小值”
给定一个长度为 N 的数组 A，要求找出一个连续子数组 [L, R]，使得表达式
的值最大。
例如输入 [1, 1, 3, 3, 1]：
- 子数组
[3, 3]：长度 = 2，最小值 = 3 → 乘积 = 6 - 子数组
[1, 1, 3, 3, 1]：长度 = 5，最小值 = 1 → 乘积 = 5
最大值为 6，即答案。
核心观察：每个元素作为最小值的贡献
任何子数组的最小值必定等于数组中某个元素 A_i。因此，我们可以枚举每个位置 i 作为当前区间的最小值，并找出以 A_i 为最小值的最长连续区间。该区间的左右边界由第一个比 A_i 小的元素决定。
✅ 这样就能确保：在该区间内，A_i 是最小值，且区间尽可能长，从而乘积最大。
单调栈高效求左右边界
使用单调递增栈（从栈底到栈顶非减）可以在线性时间内预处理每个元素的左右边界：
- 左边界
left[i]：左边第一个小于 A[i] 的元素下标；若不存在，则为-1 - 右边界
right[i]：右边第一个小于 A[i] 的元素下标；若不存在，则为n
则以 A[i] 为最小值的最长区间为 [left[i] + 1, right[i] - 1]，长度为
对应乘积为 A[i] \times \text{len}。
举例说明过程
以输入 [1, 1, 3, 3, 1] 为例：
| i | A[i] | left[i] | right[i] | 区间 | 长度 | 乘积 |
|---|---|---|---|---|---|---|
| 0 | 1 | -1 | 1 | [0, 0] | 1 | 1 |
| 1 | 1 | -1 | 4 | [0, 3] | 4 | 4 |
| 2 | 3 | 1 | 4 | [2, 3] | 2 | 6 |
| 3 | 3 | 1 | 4 | [2, 3] | 2 | 6 |
| 4 | 1 | -1 | 5 | [0, 4] | 5 | 5 |
注意：由于我们使用
>=弹出栈，相等元素不会阻挡扩展，因此A[1]=1能向左扩展到-1（因为左边没有更小的），向右扩展到4（因为A[4]=1不小于它，但我们在右边界查找时也用>=，所以停在4）。
最大乘积为 6，正确。
参考代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] A = new long[n];
for (int i = 0; i < n; i++) {
A[i] = sc.nextLong();
}
// left[i] 表示左边第一个小于 A[i] 的元素下标，不存在则为 -1
int[] left = new int[n];
// right[i] 表示右边第一个小于 A[i] 的元素下标，不存在则为 n
int[] right = new int[n];
Arrays.fill(right, n); // 默认右边界为 n（右边无更小值）
Deque<Integer> stack = new ArrayDeque<>(); // 推荐使用 ArrayDeque 而非 Stack
for (int i = 0; i < n; i++) {
// 维护单调递增栈（严格来说是非递减，但用 >= 弹出保证正确性）
while (!stack.isEmpty() && A[stack.peek()] >= A[i]) {
int idx = stack.pop();
right[idx] = i; // 被弹出元素的右边界就是 i
}
left[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(i);
}
// 枚举每个位置作为最小值，计算最大乘积
long maxProduct = 0;
for (int i = 0; i < n; i++) {
long length = right[i] - left[i] - 1;
long product = A[i] * length;
if (product > maxProduct) {
maxProduct = product;
}
}
System.out.println(maxProduct);
}
}
关键说明
- 使用
ArrayDeque：Stack是遗留类，性能较差；ArrayDeque是推荐的栈实现。 - 边界处理：
left[i] = -1和right[i] = n保证了区间长度计算正确。 - 相等元素处理：使用
>=弹出，确保相同值的元素能互相扩展，避免重复计算或遗漏。 - 时间复杂度：O(n)，每个元素入栈出栈各一次。
- 空间复杂度：O(n)，用于存储左右边界和栈。
此解法适用于 n \leq 3 \times 10^5 的大规模数据，是本题最优解。
单调栈模板
举例【73，74，75，71，69，69，72，76，73】
举例 [2, 1, 5, 6, 2, 3]
vector<int> dailyTemperatures(vector<int>& T) {
// 递增栈
stack<int> st;
vector<int> result(T.size(), 0);
st.push(0);
for (int i = 1; i < T.size(); i++) {
if (T[i] < T[st.top()]) { // 情况一
st.push(i);
} else if (T[i] == T[st.top()]) { // 情况二
st.push(i);
} else {
while (!st.empty() && T[i] > T[st.top()]) { // 情况三
result[st.top()] = i - st.top();
st.pop();
}
st.push(i);
}
}
return result;
}
精简后
vector<int> dailyTemperatures(vector<int>& T) {
stack<int> st; // 递增栈
vector<int> result(T.size(), 0);
for (int i = 0; i < T.size(); i++) {
while (!st.empty() && T[i] > T[st.top()]) { // 注意栈不能为空
result[st.top()] = i - st.top();
st.pop();
}
st.push(i);
}
return result;
}
游戏
解题思路（滑动窗口 + 单调队列）
问题转化：期望差 = 最大值期望 - 最小值期望
题目中，熊大和熊二各自独立地从所有长度为 k 的连续子数组（即滑动窗口）中等概率随机选一个。
- 设所有窗口的最大值之和为 S_{\max}
- 所有窗口的最小值之和为 S_{\min}
- 窗口总数为 T = n - k + 1
则：
✅ 目标简化为：高效计算所有长度为 k 的滑动窗口的最大值之和与最小值之和。
核心工具：单调队列求滑动窗口极值
对于“求所有滑动窗口的最大值/最小值”，标准解法是单调队列，可在 O(n) 时间内完成。
- 最大值：维护一个单调递减队列（队首始终是当前窗口最大值）
- 最小值：维护一个单调递增队列（队首始终是当前窗口最小值）
我们分别遍历一次数组，用两个单调队列，即可累加出 S_{\max} 和 S_{\min}。
单调队列工作原理（以最大值为例）
单调队列 = 双端队列（Deque） + 维护窗口内最值的候选者，按单调顺序排列。
核心思想：“过期的不要，没用的扔掉”
想象你在排队领饭，窗口大小是 k，你只能看到最近 k 个人。
你想知道：当前窗口里谁饭量最大？
- 如果前面有人饭量比你小，还排在你前面 → 他永远不可能成为最大值（因为你更大、活得更久），直接踢走！
- 如果前面有人已经不在窗口里了（太老了）→ 踢出队首！
这就是单调队列的两个操作：
- 队尾维护单调性（删没用的）
- 队首删除过期元素（删太老的）
具体操作：
我们维护一个双端队列 dq，存储数组下标，保证：
- 队列中下标对应的值单调递减（从队首到队尾）
- 队列中下标都在当前窗口 [i-k+1, i] 范围内
步骤：
- 移除过期元素：若队首下标 \leq i - k，说明已不在当前窗口，弹出。
- 维护单调性：从队尾开始，弹出所有 a[j] \leq a[i] 的下标 j（因为 a[i] 更新且更大，旧值不可能成为后续窗口最大值）。
- 加入当前下标：将 i 加入队尾。
- 记录结果：当 i \geq k-1（即第一个完整窗口形成），队首就是当前窗口最大值，累加到 S_{\max}。
最小值同理，只需将比较符号改为 \geq，维护递增队列。
举例说明过程
输入：n=3, k=2, a=[1, 2, 3]
求最大值之和 S_{\max}：
| i | 当前窗口 | 队列状态（存下标） | 队首值 | 累加 |
|---|---|---|---|---|
| 0 | [1] | [0] | — | 0 |
| 1 | [1,2] | 弹出0（因1≤2），入1 → [1] | 2 | 2 |
| 2 | [2,3] | 弹出1（因2≤3），入2 → [2] | 3 | 2+3=5 |
→ S_{\max} = 5
求最小值之和 S_{\min}：
| i | 当前窗口 | 队列状态（存下标） | 队首值 | 累加 |
|---|---|---|---|---|
| 0 | [1] | [0] | — | 0 |
| 1 | [1,2] | 2≥1，直接入1 → [0,1] | 1 | 1 |
| 2 | [2,3] | 弹出0（过期），队列=[1]；3≥2，入2 → [1,2] | 2 | 1+2=3 |
→ S_{\min} = 3
窗口总数 T = 3 - 2 + 1 = 2
答案：(5 - 3) / 2 = 1.00，与样例一致。
参考代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextLong();
}
// 计算所有长度为 k 的窗口的最大值之和
long sumMax = 0;
Deque<Integer> dqMax = new ArrayDeque<>(); // 存储下标，维护单调递减
for (int i = 0; i < n; i++) {
// 1. 移除队首过期元素（不在当前窗口 [i-k+1, i] 内）
while (!dqMax.isEmpty() && dqMax.peekFirst() <= i - k) {
dqMax.pollFirst();
}
// 2. 从队尾弹出所有小于等于 a[i] 的元素（维护递减）
while (!dqMax.isEmpty() && a[dqMax.peekLast()] <= a[i]) {
dqMax.pollLast();
}
// 3. 加入当前下标
dqMax.offerLast(i);
// 4. 当窗口形成后（i >= k-1），累加最大值
if (i >= k - 1) {
sumMax += a[dqMax.peekFirst()];
}
}
// 计算所有长度为 k 的窗口的最小值之和
long sumMin = 0;
Deque<Integer> dqMin = new ArrayDeque<>(); // 存储下标，维护单调递增
for (int i = 0; i < n; i++) {
// 1. 移除队首过期元素
while (!dqMin.isEmpty() && dqMin.peekFirst() <= i - k) {
dqMin.pollFirst();
}
// 2. 从队尾弹出所有大于等于 a[i] 的元素（维护递增）
while (!dqMin.isEmpty() && a[dqMin.peekLast()] >= a[i]) {
dqMin.pollLast();
}
// 3. 加入当前下标
dqMin.offerLast(i);
// 4. 当窗口形成后，累加最小值
if (i >= k - 1) {
sumMin += a[dqMin.peekFirst()];
}
}
// 计算期望差
int totalWindows = n - k + 1;
double result = (double) (sumMax - sumMin) / totalWindows;
// 输出保留两位小数
System.out.printf("%.2f\n", result);
}
}
关键说明
- 使用
ArrayDeque：作为双端队列实现，性能优于Stack或LinkedList。 - 两次独立遍历：一次求最大值和，一次求最小值和，逻辑清晰无耦合。
- 时间复杂度：O(n)，每个元素入队出队各一次。
- 空间复杂度：O(k)，队列最多存 k 个元素。
- 精度处理：使用
printf("%.2f")确保输出格式符合要求。
此解法直接、高效、易于理解，完全基于单调队列这一核心数据结构，适用于 n \leq 10^6 的大规模输入。
