直方图中最大矩形面积 C++完整代码

下面是使用单调栈求解直方图中最大矩形面积的C++完整代码：

#include <iostream>
#include <stack>
using namespace std;

int getMaxArea(int hist[], int n) {
    stack<int> stk;
    int maxArea = 0, area = 0, i = 0;
    while (i < n) {
        if (stk.empty() || hist[stk.top()] <= hist[i]) {
            stk.push(i++);
        } else {
            int top = stk.top();
            stk.pop();
            area = hist[top] * (stk.empty() ? i : i - stk.top() - 1);
            if (area > maxArea) {
                maxArea = area;
            }
        }
    }
    while (!stk.empty()) {
        int top = stk.top();
        stk.pop();
        area = hist[top] * (stk.empty() ? i : i - stk.top() - 1);
        if (area > maxArea) {
            maxArea = area;
        }
    }
    return maxArea;
}

int main() {
    int hist[] = {6, 2, 5, 4, 5, 1, 6};
    int n = sizeof(hist) / sizeof(hist[0]);
    cout << "The maximum area of the histogram is " << getMaxArea(hist, n) << endl;
    return 0;
}

在上述代码中，我们使用一个单调栈来维护直方图中的柱子。具体来说，我们从左到右遍历直方图中的柱子，如果当前柱子的高度不小于栈顶柱子的高度，则将当前柱子入栈；否则，我们弹出栈顶柱子，计算以该柱子高度为最小高度的矩形面积，更新最大面积值。在弹出栈顶柱子之后，当前柱子继续与栈顶柱子比较，直到当前柱子的高度不小于栈顶柱子的高度或者栈为空为止。

当所有的柱子都遍历完成后，我们需要将栈中剩余的柱子依次弹出，并根据弹出柱子的高度计算以该高度为最小高度的矩形面积，再次更新最大面积值。

最后，我们返回最大面积值即可。