洛谷（SPOJ 远程评测） SP1805 HISTOGRA - Largest Rectangle in a Histogram

// SP1805 HISTOGRA —— ★ 这一版就能 AC
//
// 本章前半章那道题的原题：柱状图里最大的矩形。
// ⚠ 但它比正文那份多了**三处不在算法里的东西**（本页第 ② 步）：
//   ① 多组数据，读到 n = 0 才结束；② n 和那 n 个高度**在同一行**；
//   ③ 每组之间栈必须清空（这里靠 top = 0 重置）。
//
// ★ 面积要开 long long：顶格 10⁵ 根 × 高 10⁹ = 10¹⁴，int 差四个数量级（本页第 ③ 步）。
#include <bits/stdc++.h>
using namespace std;

static const int N = 100005;
static long long h[N];
static int stk[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while ((cin >> n) && n) {
        for (int i = 1; i <= n; i++) cin >> h[i];
        h[n + 1] = -1;                       // ★ 哨兵：逼着循环末尾把栈清干净
        int top = 0;                         // ★ 每组重置
        long long ans = 0;
        for (int i = 1; i <= n + 1; i++) {
            while (top && h[stk[top]] >= h[i]) {
                long long H = h[stk[top]];
                top--;
                long long left = top ? stk[top] : 0;       // 左边第一个更矮的下标
                ans = max(ans, H * (i - left - 1));        // ★ 宽度 = 右界 − 左界 − 1
            }
            stk[++top] = i;
        }
        cout << ans << '\n';
    }
    return 0;
}

// SP1805 · 错法 ①：把「有多组测试数据」看漏了 —— 只处理第一组
//
// ⚠ 前面三十几道题都是「一次输入一组」，读题时那半句
//   「有多组测试数据，每组数据占一行。输入零时读入结束」很容易滑过去。
// ⇒ 它在官方样例上打出 8 就停了（该有两行）。
#include <bits/stdc++.h>
using namespace std;

static const int N = 100005;
static long long h[N];
static int stk[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    for (int i = 1; i <= n; i++) cin >> h[i];
    h[n + 1] = -1;
    int top = 0;
    long long ans = 0;
    for (int i = 1; i <= n + 1; i++) {
        while (top && h[stk[top]] >= h[i]) {
            long long H = h[stk[top]];
            top--;
            long long left = top ? stk[top] : 0;
            ans = max(ans, H * (i - left - 1));
        }
        stk[++top] = i;
    }
    cout << ans << '\n';                       // ✗ 只打了一组
    return 0;
}

// SP1805 · 错法 ②：多组之间**忘了把栈清空**
//
//   int top = 0;   ← 这一行挪到了 while 外面
//
// ⇒ 第二组开始时，栈里还压着上一组留下的下标（那些下标对应的 h[] 也还是老值）。
// ★ 这是「多组数据」这类题最经典的一发 WA，而且**第一组永远是对的** ——
//   只有一组数据时它是**精确的 0**（本页第 ④ 步：两个 bug 共用同一个盲区）。
#include <bits/stdc++.h>
using namespace std;

static const int N = 100005;
static long long h[N];
static int stk[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, top = 0;                            // ✗ top 在循环外面，组间不重置
    while ((cin >> n) && n) {
        for (int i = 1; i <= n; i++) cin >> h[i];
        h[n + 1] = -1;
        long long ans = 0;
        for (int i = 1; i <= n + 1; i++) {
            while (top && h[stk[top]] >= h[i]) {
                long long H = h[stk[top]];
                top--;
                long long left = top ? stk[top] : 0;
                ans = max(ans, H * (i - left - 1));
            }
            stk[++top] = i;
        }
        cout << ans << '\n';
    }
    return 0;
}

// SP1805 · 错法 ③：读到 EOF 才停，而不是读到 0 就停
//
//   while (cin >> n)          ← 这一版
//   while ((cin >> n) && n)   ← 正解
//
// ⇒ 末尾那个 `0` 也被当成一组数据处理了，于是多打一行 `0`。
// ★ 题面那句话是「输入零时读入结束」——**零本身不是一组数据**。
#include <bits/stdc++.h>
using namespace std;

static const int N = 100005;
static long long h[N];
static int stk[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n) {                          // ✗ 少了 && n
        for (int i = 1; i <= n; i++) cin >> h[i];
        h[n + 1] = -1;
        int top = 0;
        long long ans = 0;
        for (int i = 1; i <= n + 1; i++) {
            while (top && h[stk[top]] >= h[i]) {
                long long H = h[stk[top]];
                top--;
                long long left = top ? stk[top] : 0;
                ans = max(ans, H * (i - left - 1));
            }
            stk[++top] = i;
        }
        cout << ans << '\n';
    }
    return 0;
}

// SP1805 · 错法 ④：面积用 int
//
// 顶格 10⁵ 根 × 高 10⁹ = 10¹⁴，而 int 的上限是 2 147 483 647 —— 差 **四万倍**。
// ⚠ 而顺手写的生成器高度只有 0~10、n 只有几根 ⇒ 这一档是**精确的 0**（本页第 ③ 步）。
// ★ 演示用 unsigned 让溢出的结果可复现（第 45 章那条：别拿 UB 派生的数字当断言）。
#include <bits/stdc++.h>
using namespace std;

static const int N = 100005;
static unsigned h[N];
static int stk[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while ((cin >> n) && n) {
        for (int i = 1; i <= n; i++) cin >> h[i];
        h[n + 1] = 0u - 1u;                     // 哨兵：unsigned 里当「比谁都矮」用不了，
        int top = 0;                            //   所以这一版改成扫完再单独收尾
        unsigned ans = 0;
        for (int i = 1; i <= n; i++) {
            while (top && h[stk[top]] >= h[i]) {
                unsigned H = h[stk[top]];
                top--;
                unsigned left = top ? (unsigned)stk[top] : 0u;
                unsigned w = (unsigned)i - left - 1u;
                if (H * w > ans) ans = H * w;   // ✗ 32 位相乘，溢出就绕回去了
            }
            stk[++top] = i;
        }
        while (top) {
            unsigned H = h[stk[top]];
            top--;
            unsigned left = top ? (unsigned)stk[top] : 0u;
            unsigned w = (unsigned)n - left;
            if (H * w > ans) ans = H * w;
        }
        cout << ans << '\n';
    }
    return 0;
}