单调栈求最大矩形

【模板】单调栈求最大矩形.cpp

    auto solve = [](vi& h, int n) {
        vi L(n + 1), R(n + 1);
        // 严格递增的单调栈
        vpii inc{{0, 0}}; // pair.first 表示高度，pair.second 表示下标。假设 h[0] = -INF。
        assert(SZ(inc) == 1);
        for (int i = 1; i <= n; i++) {
            while (inc.back().first >= h[i]) {
                inc.pop_back();
            }
            L[i] = inc.back().second + 1; //左闭
            inc.eb(h[i], i);
        }
        inc ={{0, n + 1}}; // 假设 h[n + 1] = -INF。
        for (int i = n; i >= 1; i--) {
            while (inc.back().first >= h[i]) {
                inc.pop_back();
            }
            R[i] = inc.back().second; // 右开
            inc.eb(h[i], i);
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = max(ans, h[i] * (R[i] - L[i]));
        }
        return ans;
    };