给定数组，对每个窗口长度 x，求所有长度为 x 的连续区间中“区间最小值”的最大值。题目把窗口长度放在问题中心，很容易让人逐个长度扫描所有区间；真正有效的视角却是反过来问：每个元素作为区间最小值时，最多能覆盖多宽？

这个问题由左右两侧第一个更小元素决定。单调栈能在线性时间内找到边界，再利用答案随窗口变长不会上升的性质补齐空缺。

1. 官方信息与约束

547B · Mike and Feet 官方题目 于 2026-09-14 核对：难度 1900，官方标签为 binary search、data structures、dp、dsu，时间限制 1 秒，内存限制 256 MB。

题目给出长度为 n 的正整数数组。一个组必须是非空连续区间，强度定义为区间中的最小值；需要依次输出窗口长度 1..n 各自能够取得的最大强度。

官方约束 对解法的影响
1≤n≤2×10^5 需要接近 O(n) 或 O(n log n)
1≤a[i]≤10^9 元素值可用 int，无需做加法或乘法
输出全部 n 个长度 预处理后也要线性生成答案
时间限制 1 秒 避免为每个长度重扫数组

官方标签列出多种可行方向，本文采用单调栈：它最直接地表达“向左右扩展，直到遇见更小值”的边界关系。

2. 为什么按窗口长度枚举太慢

固定长度 x 时有 n-x+1 个窗口。若逐个窗口扫描其中 x 个元素求最小值，仅一个长度就可能花 O(nx)；枚举所有长度最坏达到 O(n³)。

即使用双端队列把固定长度的滑动窗口最小值降为 O(n)，仍要对 n 种长度分别运行一次，总复杂度 O(n²)。问题并不是某个固定窗口算得慢，而是不同长度之间没有共享信息。

我们改为从元素出发。对位置 i，寻找包含 i 且以 a[i] 为最小值的最大区间。假设：

  • left[i] 是 i 左侧第一个严格小于 a[i] 的位置，不存在则为 -1；
  • right[i] 是 i 右侧第一个严格小于 a[i] 的位置，不存在则为 n。

那么 a[i] 能支配的最大区间是 (left[i], right[i])，长度为：

1
width[i] = right[i] - left[i] - 1

3. 单调栈怎样找到左右边界

从左向右扫描时，栈中保存尚未遇到右侧更小值的位置，并保持对应值严格递增。处理 a[i] 前，持续弹出所有 a[stack.top()]≥a[i] 的位置；此时新的栈顶就是左侧第一个严格更小元素。

从右向左做一次对称扫描，得到右边界。两次都使用 ≥ 弹栈，等值元素不会互相阻挡，因此同一段相等值都能越过彼此，扩展到真正更小的边界。

为什么每次弹出都是安全的

假设扫描到 i 时弹出位置 j，因为 a[i]≤a[j]，对之后任何位置 k>i：

  • i 比 j 更靠近 k；
  • a[i] 又不大于 a[j]。

若未来只想寻找“左侧最近且更小”的候选，j 已经不可能优于 i。它可以永久离开栈。每个位置最多入栈一次、出栈一次，所以一次扫描为 O(n)。

4. 手工演算边界

以数组 [2, 1, 4, 5, 1, 3, 3] 为例：

i a[i] left[i] right[i] width[i] 解释
0 2 -1 1 1 左侧无更小值，右侧的 1 阻挡
1 1 -1 7 7 没有严格更小值，可覆盖全数组
2 4 1 4 2 可覆盖 [4,5]
3 5 2 4 1 两侧很快遇见更小值
4 1 -1 7 7 与另一个 1 相等，不互相阻挡
5 3 4 7 2 可覆盖末尾两个 3
6 3 4 7 2 等值元素共享同一严格更小边界

先把每个元素投放到它的最大宽度：

1
best[width[i]] = max(best[width[i]], a[i])

这时只直接得到某些长度的候选。例如上表会更新 best[1]=5、best[2]=4、best[7]=1，长度 3 到 6 暂时没有元素恰好以这些长度作为最大支配宽度。

5. 为什么还需要从长到短回填

设 answer[x] 为长度 x 的所有窗口最小值中的最大值。窗口变长时，可选区间的最小值不可能整体变得更高，因此：

1
answer[x] >= answer[x + 1]

更具体地说，若某个值 v 能作为长度 L 区间的最小值，那么从这个区间中截取任何更短的非空连续片段，只要保留产生 v 的位置，就能让片段内所有值仍不小于 v。所以 v 对所有 x≤L 都是可行候选。

因此从 n-1 递减到 1 执行：

1
best[x] = max(best[x], best[x + 1])

这一步不是经验修补，而是在传播“长区间可行，则更短区间也可行”的包含关系。

6. 正确性证明

引理一：边界区间内 a[i] 是最小值

left[i] 与 right[i] 分别是两侧第一个严格小于 a[i] 的位置。因此所有满足 left[i]<j<right[i] 的元素都有 a[j]≥a[i]，且区间包含 i，所以该区间最小值正是 a[i]。

引理二：width[i] 是 a[i] 能作为最小值覆盖的最大长度

向左再扩一位会包含严格更小的 a[left[i]]，向右再扩一位会包含严格更小的 a[right[i]]；存在数组边界时也无法继续扩展。结合引理一，right[i]-left[i]-1 恰为最大长度。

引理三：回填后 best[x] 不小于任意长度 x 窗口的最小值

任取长度 x 的窗口，并选择其中一个最小值位置 i。该窗口证明 a[i] 至少能覆盖长度 x，所以 width[i]≥x。算法先用 a[i] 更新 best[width[i]]，再从长到短传播到 best[x]，因此 best[x]≥a[i]。

引理四：回填后的每个 best[x] 都能由某个长度 x 的窗口取得

best[x] 的值来自某个位置 i，且 width[i]≥x。在 i 的最大支配区间内总能截取一个包含 i 的长度 x 子区间；由引理一，其最小值是 a[i]=best[x]。所以算法不会产生不可实现的答案。

定理：算法输出每种窗口长度的最大强度

引理三说明算法值不小于最优答案，引理四说明算法值本身可行，故两者相等。对所有 x=1..n 都成立。

7. 完整 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> height(n);
    for (int& value : height) cin >> value;

    vector<int> left(n), right(n);
    vector<int> stack;
    stack.reserve(n);

    for (int i = 0; i < n; ++i) {
        while (!stack.empty() && height[stack.back()] >= height[i]) {
            stack.pop_back();
        }
        left[i] = stack.empty() ? -1 : stack.back();
        stack.push_back(i);
    }

    stack.clear();
    for (int i = n - 1; i >= 0; --i) {
        while (!stack.empty() && height[stack.back()] >= height[i]) {
            stack.pop_back();
        }
        right[i] = stack.empty() ? n : stack.back();
        stack.push_back(i);
    }

    vector<int> best(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        int width = right[i] - left[i] - 1;
        best[width] = max(best[width], height[i]);
    }

    for (int width = n - 1; width >= 1; --width) {
        best[width] = max(best[width], best[width + 1]);
    }

    for (int width = 1; width <= n; ++width) {
        if (width > 1) cout << ' ';
        cout << best[width];
    }
    cout << '\n';
}

两次单调栈扫描、一次投放和一次回填都是 O(n)，总时间 O(n)；左右边界、栈与答案数组占 O(n) 空间。

8. 重复值与边界错误清单

场景 正确处理 常见错误
所有值相等 每个长度答案都相同 让相等值互相阻挡，区间被切碎
严格递增 左边界紧邻，右边界为 n 忘记虚拟边界导致长度少 1
严格递减 左边界为 -1，右边界紧邻 栈比较方向写反
n=1 唯一答案是 a[0] 回填循环越界
最大宽度为 L 先更新 best[L] 把数组下标 i 当作窗口长度
某长度未直接更新 从更长长度向短长度传播 输出初始值 0
左右边界 都寻找严格更小值 一边的等号处理不一致却没有证明

9. 独立验证

tests/verify-mike-feet-article.cjs 会提取并以 -std=c++17 -Wall -Wextra -pedantic 编译本文代码，要求编译器零警告。参考实现枚举每个窗口长度、每个连续区间，再直接扫描区间求最小值；它不使用单调栈、支配区间或答案回填。

验证覆盖官方样例、单元素、全相等、严格递增、严格递减、大量重复值和固定种子随机数组，并加入长度 20 万的递增数组检查线性实现与输出规模。掌握这题后，再看柱状图最大矩形、贡献计数与“每个元素作为最小值影响哪些区间”会更自然。