题解

题目描述

在横轴上有 $n$ 个宽度均为 1 的相邻矩形，第 $i$ 个矩形的高度为 $h_i$，它们共同构成了一个直方图。普通的「最大矩形面积」问题是：在不改变顺序的前提下，找到可以完全覆盖在直方图之下的、面积最大的矩形。

本题在此基础上允许你 执行一次任意两根柱子高度的交换，问：在进行至多一次交换之后，能得到的最大矩形面积是多少？

思路解析

1. 不交换时的基准答案 首先，可以用「单调栈」算法在 $O(n)$ 时间内求出不做任何交换时的最大矩形面积，记为 base。

2. 交换带来的增益 对于每根柱子 $i$（高度为 $H=h_i$），如果我们想让以它为「高度」的矩形尽可能宽，就需要：

   • 找到原柱子 $i$ 两侧向外延伸，直到遇到高度小于 $H$ 的位置，这可通过「稀疏表」支持的区间最小值查询（RMQ）在 $O(\log n)$ 时间内完成，得到一段连续区间 $[L_0, R_0]$ 内所有高度都 $\ge H$。

   • 由于允许一次交换，我们还可以再「引入」另外一个高度至少 $H$ 的柱子到这段区间的外侧。具体做法是：

     1. 统计全局有多少柱子高度 $\ge H$，设为 count_good。

     2. 在 $[0, L_0-1]$ 和 $[R_0+1, n-1]$ 两侧，再各自找出最长的所有高度 $\ge H$ 的连续子段，长度分别为 w_left 和 w_right。

     3. 将 $i$ 位置的柱子和「一端」延伸段上的某个柱子交换后，最大宽度最多可达

        $w = (R_0 - L_0 + 1) + 1 + max(w_{left},w_{right})$

        但由于可用的高度 $\ge H$ 的柱子总数只有 count_good 根，真实宽度要取 $min(w,{count_good})$。

   这样，对于每个 $i$ 都算一个可达面积 $H min(w,{count_good})$，再与 base 取最大即可。

3. 复杂度

   • 构建稀疏表：$O(n\log n)$
   • 单调栈基准解：$O(n)$
   • 枚举每根柱子，进行常数次 RMQ（二分查找配合 RMQ 共 $O(\log n)$）：$O(n\log n)$
   • 总体：$O(n\log n)$，可应对 $n\le10^5$。

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct SparseTable {
    int n, LOG;
    vector<int> log2;
    vector<vector<int>> st;

    SparseTable(const vector<int>& a) {
        n = a.size();
        log2.resize(n + 1);
        log2[1] = 0;
        for (int i = 2; i <= n; i++)
            log2[i] = log2[i / 2] + 1;
        LOG = log2[n];

        st.assign(LOG + 1, vector<int>(n));
        st[0] = a;
        for (int k = 1; k <= LOG; k++) {
            int len = 1 << k;
            int half = len >> 1;
            for (int i = 0; i + len <= n; i++) {
                st[k][i] = min(st[k-1][i], st[k-1][i + half]);
            }
        }
    }

    // query min on [l..r], 0-based inclusive
    int query(int l, int r) const {
        if (l > r) return INT_MAX;
        int len = r - l + 1;
        int k = log2[len];
        return min(st[k][l], st[k][r - (1<<k) + 1]);
    }
};

// standard largest-rectangle-in-histogram, O(n)
ll maxAreaNoSwap(const vector<int>& h) {
    int n = h.size();
    stack<int> st;
    st.push(-1);
    ll ans = 0;
    for (int i = 0; i <= n; i++) {
        int cur = (i == n ? 0 : h[i]);
        while (st.top() != -1 && h[st.top()] >= cur) {
            int height = h[st.top()];
            st.pop();
            int width = i - st.top() - 1;
            ans = max(ans, (ll)height * width);
        }
        st.push(i);
    }
    return ans;
}

// find the smallest idx in [l..r] s.t. check(idx) is true, or -1 if none
int findLeftmost(int l, int r, const function<bool(int)>& check) {
    int ans = -1;
    while (l <= r) {
        int m = (l + r) >> 1;
        if (check(m)) {
            ans = m;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    return ans;
}

// find the largest idx in [l..r] s.t. check(idx) is true, or -1 if none
int findRightmost(int l, int r, const function<bool(int)>& check) {
    int ans = -1;
    while (l <= r) {
        int m = (l + r) >> 1;
        if (check(m)) {
            ans = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return ans;
}

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

    int n;
    if (!(cin >> n)) return 0;
    vector<int> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }

    // 1) baseline without any swap
    ll max_area = maxAreaNoSwap(h);

    // 2) build RMQ & sorted array
    SparseTable st(h);
    vector<int> hs = h;
    sort(hs.begin(), hs.end());

    // 3) for each position, consider swapping that bar outward
    for (int i = 0; i < n; i++) {
        int H = h[i];
        // how many bars >= H
        int cnt_smaller = int(lower_bound(hs.begin(), hs.end(), H) - hs.begin());
        int count_good = n - cnt_smaller;

        // center segment [l0..r0] where all >= H
        int l0 = findLeftmost(0, i, [&](int x){
            return st.query(x, i) >= H;
        });
        int r0 = findRightmost(i, n-1, [&](int x){
            return st.query(i, x) >= H;
        });
        if (l0 == -1 || r0 == -1) continue;
        int w0 = r0 - l0 + 1;

        // possible extra on left of l0-1
        int w_left = 0;
        if (l0 >= 2) {
            int end = l0 - 2;
            int start = findLeftmost(0, end, [&](int x){
                return st.query(x, end) >= H;
            });
            if (start != -1) {
                w_left = end - start + 1;
            }
        }

        // possible extra on right of r0+1
        int w_right = 0;
        if (r0 + 2 <= n-1) {
            int start = r0 + 2;
            int end = findRightmost(start, n-1, [&](int x){
                return st.query(start, x) >= H;
            });
            if (end != -1) {
                w_right = end - start + 1;
            }
        }

        // by swapping h[i] with one bar outside center, width = w0 + 1 + max(w_left, w_right)
        int w_swap = w0 + 1 + max(w_left, w_right);
        int achievable = min(w_swap, count_good);
        max_area = max(max_area, (ll)H * achievable);
    }

    cout << max_area << "\n";
    return 0;
}

Python

import sys
import threading
def main():
    import bisect
    input = sys.stdin.readline

    n = int(input())
    h = list(map(int, input().split()))

    # 1) 基准：单调栈求最大矩形
    def max_area_no_swap(h):
        st = [-1]
        ans = 0
        for i in range(len(h)+1):
            cur = 0 if i==len(h) else h[i]
            while st[-1] != -1 and h[st[-1]] >= cur:
                H = h[st.pop()]
                W = i - st[-1] - 1
                ans = max(ans, H*W)
            st.append(i)
        return ans

    base = max_area_no_swap(h)

    # 2) 构建稀疏表 RMQ（区间最小值）
    LOG = (n).bit_length()
    st = [h[:]]
    for k in range(1, LOG):
        prev = st[k-1]
        curr = [min(prev[i], prev[i+(1<<(k-1))]) for i in range(n-(1<<k)+1)]
        st.append(curr)
    log2 = [0]*(n+1)
    for i in range(2, n+1):
        log2[i] = log2[i//2] + 1
    def rmq(l, r):
        k = log2[r-l+1]
        return min(st[k][l], st[k][r-(1<<k)+1])

    # 3) 排序统计 >= H 的数量
    hs = sorted(h)
    def count_ge(x):
        # 第一个 >= x 的索引
        idx = bisect.bisect_left(hs, x)
        return n - idx

    # 二分查找辅助
    def find_leftmost(L, R, H):
        ans = -1
        l, r = L, R
        while l <= r:
            m = (l+r)//2
            if rmq(m, R) >= H:
                ans = m
                r = m-1
            else:
                l = m+1
        return ans

    def find_rightmost(L, R, H):
        ans = -1
        l, r = L, R
        while l <= r:
            m = (l+r)//2
            if rmq(L, m) >= H:
                ans = m
                l = m+1
            else:
                r = m-1
        return ans

    ans = base
    for i, H in enumerate(h):
        # 中心最大区间 [l0..r0]
        l0 = find_leftmost(0, i, H)
        r0 = find_rightmost(i, n-1, H)
        if l0==-1 or r0==-1: 
            continue
        w0 = r0 - l0 + 1

        # 左侧延伸
        w_left = 0
        if l0 >= 2:
            end = l0 - 2
            stl = find_leftmost(0, end, H)
            if stl != -1:
                w_left = end - stl + 1

        # 右侧延伸
        w_right = 0
        if r0+2 <= n-1:
            stp = find_rightmost(r0+2, n-1, H)
            if stp != -1:
                w_right = stp - (r0+2) + 1

        total_good = count_ge(H)
        w = w0 + 1 + max(w_left, w_right)
        w = min(w, total_good)
        ans = max(ans, w * H)

    print(ans)

if __name__ == "__main__":
    threading.Thread(target=main).start()

Java

import java.io.*;
import java.util.*;

public class Main {
    static int n;
    static int[] h;
    static int[][] st;
    static int[] log2;

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(in.readLine());
        h = Arrays.stream(in.readLine().split("\\s+"))
                  .mapToInt(Integer::parseInt).toArray();

        long base = maxAreaNoSwap();

        buildSparseTable();
        int[] hs = Arrays.copyOf(h, n);
        Arrays.sort(hs);

        long ans = base;
        for (int i = 0; i < n; i++) {
            int H = h[i];
            int l0 = findLeftmost(0, i, H);
            int r0 = findRightmost(i, n-1, H);
            if (l0 < 0 || r0 < 0) continue;
            int w0 = r0 - l0 + 1;

            int wLeft = 0;
            if (l0 >= 2) {
                int end = l0 - 2;
                int stl = findLeftmost(0, end, H);
                if (stl >= 0) wLeft = end - stl + 1;
            }

            int wRight = 0;
            if (r0 + 2 <= n-1) {
                int str = findRightmost(r0 + 2, n-1, H);
                if (str >= 0) wRight = str - (r0+2) + 1;
            }

            int totalGood = n - (Arrays.binarySearch(hs, H) < 0
                               ? -Arrays.binarySearch(hs, H)-1
                               : Arrays.binarySearch(hs, H));
            int w = w0 + 1 + Math.max(wLeft, wRight);
            w = Math.min(w, totalGood);
            ans = Math.max(ans, 1L * H * w);
        }

        System.out.println(ans);
    }

    // 单调栈求基准解
    static long maxAreaNoSwap() {
        Deque<Integer> st = new ArrayDeque<>();
        st.push(-1);
        long res = 0;
        for (int i = 0; i <= n; i++) {
            int cur = (i == n ? 0 : h[i]);
            while (st.peek() != -1 && h[st.peek()] >= cur) {
                int height = h[st.pop()];
                int width = i - st.peek() - 1;
                res = Math.max(res, 1L*height*width);
            }
            st.push(i);
        }
        return res;
    }

    // 构建稀疏表
    static void buildSparseTable() {
        log2 = new int[n+1];
        for (int i = 2; i <= n; i++)
            log2[i] = log2[i/2] + 1;
        int K = log2[n] + 1;
        st = new int[K][n];
        System.arraycopy(h, 0, st[0], 0, n);
        for (int k = 1; k < K; k++) {
            for (int i = 0; i + (1<<k) <= n; i++) {
                st[k][i] = Math.min(st[k-1][i], st[k-1][i + (1<<(k-1))]);
            }
        }
    }

    // 区间最小值查询
    static int rmq(int l, int r) {
        int k = log2[r-l+1];
        return Math.min(st[k][l], st[k][r-(1<<k)+1]);
    }

    static int findLeftmost(int L, int R, int H) {
        int ans = -1, l = L, r = R;
        while (l <= r) {
            int m = (l+r)>>1;
            if (rmq(m, R) >= H) {
                ans = m; r = m-1;
            } else {
                l = m+1;
            }
        }
        return ans;
    }

    static int findRightmost(int L, int R, int H) {
        int ans = -1, l = L, r = R;
        while (l <= r) {
            int m = (l+r)>>1;
            if (rmq(L, m) >= H) {
                ans = m; l = m+1;
            } else {
                r = m-1;
            }
        }
        return ans;
    }
}

题目内容

小华之前玩过一个游戏，在横轴上放了$n$ 个相邻的矩形，每个矩形的宽度是 $1$ ，而第 $i(1≦i≦n)$ 个矩形的高度为 $h_i$，这 $n$ 个矩形构成了一个直方图，在直方图中找出能够勾勒出来的矩形的最大面积。

这个游戏小华已经玩得很腻了，于是小华就想增加一下难度，现在有 $1$ 次交换任意 $2$ 个矩形的操作，请问在交换后，能够勾勒出的最大的短形面积能达到多少呢?

输入描述

第一行包含一个整数 $n(2≦n≦10^5)$，表示矩形个数。

第二行包含 $n$ 个整数，依次为 $h_1,h_2,..., h_n(1 ≦ h_i≦ 10^4)$ ，表示矩形的高度。

输出描述

输出一个整数，表示在交换后能够勾勒出的最大的矩形面积。

样例1

输入

6
3 1 6 5 2 3

输出

12

说明

交换第 $2$ 个与第 $6$ 个元素，数组变为 $[3,3,6,5,2,1]$ ，此时前 $4$ 项面积最大为 $12$ 。

样例2

输入

7
5 5 3 5 5 2 4

输出

20

说明

交换第 $3$ 个与第 $7$ 个元素，数组变为 $[5,5,4,5,5,2,3]$ ，此时前 $5$ 项面积最大为 $2 0$ 。