在 NOI 竞赛中，构造“柱状图最大矩形”的数据时，必须针对单调栈的特性构造：单调递增序列（考察栈的深度）、单调递减序列（考察出栈结算）、锯齿形序列（考察频繁出栈入栈）以及全等序列（考察对等于高度的处理）。

以下是完整的测试数据生成器，它将自动生成 1.in/1.out 到 10.in/10.out。

【数据生成器 C++ 代码】

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <random>
#include <algorithm>
#include <stack>

using namespace std;

typedef long long ll;

// --- 标准答案算法 (O(n) 单调栈) ---
// 使用迭代写法，添加首尾哨兵，保证不爆栈且逻辑严密
ll solve(int n, vector<int>& h) {
    // 构造带哨兵的临时数组
    vector<int> heights;
    heights.push_back(0); // 左哨兵
    for (int x : h) heights.push_back(x);
    heights.push_back(0); // 右哨兵

    int m = heights.size();
    static int stk[100005 + 2]; // 静态数组模拟栈
    int top = 0;
    ll max_area = 0;

    for (int i = 0; i < m; i++) {
        // 当发现当前高度破坏了栈的单调递增性时，结算
        while (top > 0 && heights[i] < heights[stk[top]]) {
            int mid = stk[top--];
            int height = heights[mid];
            int width = i - stk[top] - 1;
            max_area = max(max_area, (ll)height * width);
        }
        stk[++top] = i;
    }
    return max_area;
}

// --- 文件读写辅助 ---
void writeData(int id, int n, const vector<int>& h) {
    // 写入输入文件
    string inName = to_string(id) + ".in";
    ofstream fout(inName);
    fout << n << "\n";
    for (int i = 0; i < n; i++) {
        fout << h[i] << (i == n - 1 ? "" : " ");
    }
    fout << endl;
    fout.close();

    // 计算答案并写入输出文件
    vector<int> h_copy = h;
    ll ans = solve(n, h_copy);
    string outName = to_string(id) + ".out";
    ofstream fans(outName);
    fans << ans << endl;
    fans.close();
}

int main() {
    // 随机数引擎
    mt19937 rng(20251223);
    auto getRand = [&](int l, int r) {
        return uniform_int_distribution<int>(l, r)(rng);
    };

    for (int t = 1; t <= 10; t++) {
        int n;
        vector<int> h;

        if (t == 1) { // 样例数据
            n = 6; h = {2, 1, 5, 6, 2, 3};
        } 
        else if (t == 2) { // 边界：最小 n
            n = 1; h = {getRand(0, 10000)};
        }
        else if (t == 3) { // 边界：所有高度相等 (最大面积 n * h)
            n = 100000;
            h.assign(n, 10000);
        }
        else if (t == 4) { // 严格递增序列
            n = 100000;
            for (int i = 1; i <= n; i++) h.push_back(i % 10001);
            sort(h.begin(), h.end());
        }
        else if (t == 5) { // 严格递减序列
            n = 100000;
            for (int i = n; i >= 1; i--) h.push_back(i % 10001);
            sort(h.begin(), h.end(), greater<int>());
        }
        else if (t == 6) { // 锯齿形序列 (10000, 1, 10000, 1...)
            n = 100000;
            for (int i = 0; i < n; i++) h.push_back(i % 2 == 0 ? 10000 : 1);
        }
        else if (t == 7) { // 随机小规模 (容易目测调试)
            n = 100;
            for (int i = 0; i < n; i++) h.push_back(getRand(0, 100));
        }
        else if (t == 8) { // 包含大量高度为 0 的柱子 (切断矩形)
            n = 100000;
            for (int i = 0; i < n; i++) h.push_back(getRand(0, 10) == 0 ? 0 : getRand(1, 10000));
        }
        else if (t == 9) { // 随机大规模 A
            n = 80000;
            for (int i = 0; i < n; i++) h.push_back(getRand(0, 10000));
        }
        else { // 随机大规模 B
            n = 100000;
            for (int i = 0; i < n; i++) h.push_back(getRand(0, 10000));
        }

        writeData(t, n, h);
        cout << "Test Case " << t << " finished. N=" << n << endl;
    }

    return 0;
}

测试点设计逻辑说明：

1. 测试点 1 (Sample)：确保程序能通过官方样例。
2. 测试点 2 (Mini)：$N=1$ 是最容易被忽视的边界，测试初始化是否正确。
3. 测试点 3 (Flat)：全相等序列。测试对 heights[i] == heights[stk[top]] 情况的处理，此时宽度应能正确跨越整个数组。
4. 测试点 4 (Increasing)：测试栈的增长上限，确保栈数组没有开小。
5. 测试点 5 (Decreasing)：测试连续弹栈逻辑。
6. 测试点 6 (Sawtooth)：测试极端频繁的入栈和出栈切换。
7. 测试点 7 (Small Random)：用于在选手本地调试时提供易读的小规模数据。
8. 测试点 8 (Sparse)：大量高度为 0 的柱子会将直方图分割成许多小的孤立区域，考察程序是否会因为中间高度为 0 而逻辑中断。
9. 测试点 9-10 (Large Random)：$10^5$ 级别的综合压力测试。

生成器技术细节：

• 哨兵实现：在 solve 函数中，通过向 vector 插入首尾 0，确保了所有有效数据都能被弹出并计算。这是解决本题最稳健的方法。
• 避免爆栈：该算法是纯迭代（for 循环嵌套 while 弹出），没有递归调用。即便 $N=10^6$，也只受限于内存大小（Memory Limit），不会产生栈溢出（Stack Overflow）。
• 长整型安全：面积计算使用了 (ll)height * width。在 $N=10^5, H=10^4$ 的极限下，答案为 $10^9$，虽然在 int 范围内，但为了防止题目变体（如 $H=10^9$），代码中使用了 long long 保证通用性。
• 内存优化：stk 数组使用 static 修饰，避免在 10 次测试点生成的循环中反复在栈内存上分配大块空间。

你好，同学。这道题是单调栈的高级应用。在处理这类“高度受限”的区间问题时，单调栈能帮我们迅速锁定“左右边界”。

以下是按照 NOIP 竞赛标准编写的 C++14 代码，使用了哨兵技巧和手动模拟栈来保证最优性能。

【标准题解代码】

#include <cstdio>
#include <algorithm>

using namespace std;

/**
 * 易错点 1：数据范围。
 * n = 10^5, h = 10^4，最大面积可能达到 10^9。
 * 虽然 int 极限是 2.1e9，但在计算过程中使用 long long 是保险的做法，
 * 尤其是在题目变体中数据范围更大时。
 */
typedef long long ll;

const int MAXN = 100005;
int h[MAXN];    // 存储高度
int stk[MAXN];  // 手写栈，存储下标
int top = 0;    // 栈顶指针

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;

    /**
     * 关键点 2：哨兵 (Sentinel) 技巧。
     * 我们在高度数组的首尾各添加一个高度为 0 的柱子。
     * - 左侧的 0：保证栈永远不会为空（栈底始终有一个 0），避免 while 循环中判断 stack.empty()。
     * - 右侧的 0：保证遍历结束时，栈中所有剩余的柱子都能被弹出并计算面积。
     */
    h[0] = 0; 
    for (int i = 1; i <= n; i++) {
        scanf("%d", &h[i]);
    }
    h[n + 1] = 0;

    ll max_area = 0;
    
    // 放入第一个哨兵的下标
    stk[++top] = 0;

    // 遍历从 1 到 n+1（包含右哨兵）
    for (int i = 1; i <= n + 1; i++) {
        /**
         * 维护一个单调递增栈。
         * 如果当前柱子比栈顶矮，说明以栈顶柱子为高度的矩形无法再向右延伸了。
         */
        while (top > 0 && h[i] < h[stk[top]]) {
            int mid = stk[top--]; // 确定要计算哪根柱子的高度
            int height = h[mid];
            
            /**
             * 关键点 3：计算宽度。
             * 此时栈顶剩下的元素，就是 mid 柱子左边第一个比它矮的柱子。
             * 当前的 i，就是 mid 柱子右边第一个比它矮的柱子。
             * 所以宽度 w = (右边界 - 左边界 - 1) = (i - stk[top] - 1)。
             */
            int width = i - stk[top] - 1;
            
            ll current_area = (ll)height * width;
            if (current_area > max_area) {
                max_area = current_area;
            }
        }
        // 当前柱子下标入栈
        stk[++top] = i;
    }

    printf("%lld\n", max_area);

    return 0;
}

二、 复杂度分析思考过程

1. 时间复杂度：$O(n)$

• 思考过程：
  • 外层 for 循环从 $0$ 到 $n+1$，总计 $n+2$ 次。
  • 内层 while 循环：虽然看似嵌套，但请观察 stk。每个下标 $i$ 只会在 for 循环末尾执行一次 stk[++top]（入栈），并且在 while 逻辑中被执行一次 top--（出栈）。
  • 结论：总的操作次数是 $2 \times (n+2)$。时间复杂度为线性的 $O(n)$。在 $10^5$ 规模下，执行时间通常在 20ms 以内。

2. 空间复杂度：$O(n)$

• 思考过程：
  • h[] 数组占用 $MAXN \times 4$ 字节。
  • stk[] 数组占用 $MAXN \times 4$ 字节。
  • 总占用空间约为 $0.8$ MB。
  • 结论：在 256MB 的限制下，绰绰有余。

三、 时间复杂度优化建议

虽然 $O(n)$ 已经是理论最优复杂度，但在竞赛（尤其是大数据量 $10^6$）中，我们可以做如下微调：

1. 快读 (Fast I/O)： 如果 $n$ 的范围进一步扩大，scanf 可能会成为瓶颈。使用 getchar 封装的 read() 函数能显著提升读入速度。

2. 避免强制类型转换： 虽然我们在计算 height * width 时用了 (ll)，如果对常数极其敏感，可以预先将 h[] 数组定义为 long long，减少类型转换指令。

3. 哨兵的硬编码： 如果你不想修改原数组 h[]，也可以在循环内部通过逻辑判断模拟哨兵，但这样会增加 if-else 分支预测失败的概率，通常不建议。

四、 关键逻辑总结 (避坑指南)

• 宽度计算公式：很多同学会写错成 i - mid 或者 i - stk[top]。请务必记住：矩形是跨越在左右两个“矮子”之间的空隙里，所以是 $i - stk[top] - 1$。
• 栈内存放的是什么：单调栈通常存放下标而不是具体数值。因为下标既能帮我们找到高度（h[stk[top]]），又能帮我们计算宽度（i - stk[top]）。
• 等于高度的处理：当 h[i] == h[stk[top]] 时，可以入栈也可以不处理（弹出后再压入）。在本题中，由于我们要找的是“第一个比自己矮的”，相等的柱子不会限制高度，因此可以合并到 h[i] >= h[stk[top]] 的情况中。

教练寄语： 单调栈是一种“延迟结算”的艺术。每一个入栈的元素都在等待属于它的“右边界”。一旦边界出现，它就完成使命，贡献出它的面积。掌握了哨兵和宽度公式，你就掌握了这道题的灵魂。