题目链接

直方图中最大矩形面积

题目描述

给定一个由 个宽度为 的相邻矩形组成的直方图，第 个矩形的高度为 。你需要计算这个直方图中可以构成的最大矩形的面积。

解题思路

这是一个经典的算法问题。核心思想是，对于每个矩形条 ，如果我们将其作为最终最大矩形的高，那么我们需要找到这个矩形可以向左和向右延伸的最大宽度。这个宽度由其左右两侧第一个比它矮的矩形条所决定。

一个朴素的解法是遍历每个矩形条 ，然后分别向左和向右扫描，找到第一个高度小于 的边界，从而确定宽度并计算面积。这种方法的时间复杂度为 ，对于较大的 会超时。

更高效的解法是使用单调栈，可以在 的时间内解决此问题。我们维护一个单调递增的栈，栈中存储的是矩形条的索引。

算法流程：

  1. 初始化一个空栈 st 和一个最大面积 max_area = 0。
  2. 遍历每个矩形条 从 到 ：
    a. 当栈不为空，并且当前矩形条 的高度小于栈顶索引对应的矩形条高度 h[st.top()] 时，说明我们找到了栈顶矩形条的右边界。
    b. 此时，我们将栈顶索引 top_idx 弹出。这个弹出的矩形条就是我们要计算面积的矩形，其高度为 h[top_idx]。 c. 它的右边界是当前索引 。它的左边界是弹出 top_idx 后的新栈顶索引 st.top()。因此，宽度为 。如果弹出后栈为空，说明左边界可以延伸到最左边，宽度为 。
    d. 计算面积 h[top_idx] * width，并更新 max_area。
    e. 重复这个弹出过程，直到栈为空或当前矩形条 不再小于栈顶矩形条的高度。
    f. 将当前矩形条的索引 压入栈中。
  3. 遍历完所有矩形条后，栈中可能还剩下一些索引。这些索引对应的矩形条的右边界都延伸到了最右端。我们需要对它们进行清算。
    a. 依次弹出栈中剩余的索引 top_idx。
    b. 其高度为 h[top_idx]。右边界为 。左边界为新栈顶或 。宽度为 （或 如果栈为空）。
    c. 计算面积并更新 max_area。

为了简化代码，我们可以在原始高度数组的末尾添加一个高度为 的“哨兵”矩形条。这可以确保在遍历结束后，栈中所有的元素都会被正确地弹出并计算，从而无需在循环后进行额外的清算步骤。

代码

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

void solve() {
    using namespace std;
    int n;
    cin >> n;
    vector<long long> h(n);
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }

    stack<int> st;
    long long max_area = 0;
    
    // 添加哨兵
    h.push_back(0);

    for (int i = 0; i < h.size(); ++i) {
        while (!st.empty() && h[st.top()] >= h[i]) {
            int top_idx = st.top();
            st.pop();
            long long height = h[top_idx];
            long long width = st.empty() ? i : (i - st.top() - 1);
            max_area = max(max_area, height * width);
        }
        st.push(i);
    }

    cout << max_area << endl;
}

int main() {
    using namespace std;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }

    private static void solve(Scanner sc) {
        int n = sc.nextInt();
        long[] h = new long[n + 1]; // +1 for sentinel
        for (int i = 0; i < n; i++) {
            h[i] = sc.nextLong();
        }
        h[n] = 0; // Sentinel

        Stack<Integer> st = new Stack<>();
        long maxArea = 0;

        for (int i = 0; i < h.length; i++) {
            while (!st.isEmpty() && h[st.peek()] >= h[i]) {
                int topIdx = st.pop();
                long height = h[topIdx];
                long width = st.isEmpty() ? i : (i - st.peek() - 1);
                maxArea = Math.max(maxArea, height * width);
            }
            st.push(i);
        }
        System.out.println(maxArea);
    }
}

import sys

def solve():
    n = int(sys.stdin.readline())
    h = list(map(int, sys.stdin.readline().split()))
    
    # 添加哨兵
    h.append(0)
    
    st = [] # 存储索引
    max_area = 0
    
    for i, height in enumerate(h):
        while st and h[st[-1]] >= height:
            top_idx = st.pop()
            h_top = h[top_idx]
            width = i if not st else i - st[-1] - 1
            max_area = max(max_area, h_top * width)
        st.append(i)
        
    print(max_area)

def main():
    t = int(sys.stdin.readline())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法: 单调栈
  • 时间复杂度: ，因为每个矩形条的索引最多被压入和弹出栈一次。
  • 空间复杂度: ，在最坏情况下（例如高度严格递增的序列），所有索引都会被压入栈中。