标准做法是双指针。但第一次做的时候感觉很难想到，所以写一下$O(n \log n)$的做法。

算法：单调栈+二分

时间复杂度：$O(n \log n)$

C++

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 100010;

int n, ans = -1;
int h[N], ls[N], rs[N]; // ls为以左边界枚举，rs为以右边界枚举
int l_idx = -1, r_idx = -1; 

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &h[i]);
    for (int i = 0; i < n; i++) {
        int l = 0, r = l_idx;
        while (l < r) {
            int mid = l + r >> 1;
            if (h[ls[mid]] >= h[i]) r = mid;
            else l = mid + 1;
        }
        if (l <= l_idx && h[ls[l]] >= h[i]) ans = max(ans, h[i] * (i - ls[l]));
        if (l_idx < 0 || h[i] > h[ls[l_idx]]) ls[++l_idx] = i;
    }
    for (int i = n - 1; i >= 0; i--) {
        int l = 0, r = r_idx;
        while (l < r) {
            int mid = l + r >> 1;
            if (h[rs[mid]] >= h[i]) r = mid;
            else l = mid + 1;
        }
        if (l <= r_idx && h[rs[l]] >= h[i]) ans = max(ans, h[i] * (rs[l] - i));
        if (r_idx < 0 || h[i] > h[rs[r_idx]]) rs[++r_idx] = i;
    }
    printf("%d\n", ans);
    return 0;
}

leetcode

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size(), ans = -1;
        vector<int> rs, ls;
        for (int i = 0; i < n; i++) {
            int l = 0, r = rs.size() - 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (height[rs[mid]] >= height[i]) r = mid;
                else l = mid + 1;
            }
            if (rs.size() && height[rs[l]] >= height[i]) ans = max(ans, height[i] * (i - rs[l]));
            if (rs.empty() || height[i] > height[rs.back()]) rs.push_back(i);
        }
        for (int i = n - 1; i >= 0; i--) {
            int l = 0, r = ls.size() - 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (height[ls[mid]] >= height[i]) r = mid;
                else l = mid + 1;
            }
            if (ls.size() && height[ls[l]] >= height[i]) ans = max(ans, height[i] * (ls[l] - i));
            if (ls.empty() || height[i] > height[ls.back()]) ls.push_back(i);
        }
        return ans;
    }
};