柱状图中最大的矩形c++

求解柱状图中最大的矩形，可以使用单调栈来实现。具体思路如下：

1. 创建一个栈，用来存储柱子的索引。同时，创建一个数组 heights，用来存储柱子的高度。

2. 遍历 heights 数组，对于每个柱子，进行如下操作：

a. 如果栈为空，或者当前柱子的高度大于等于栈顶柱子的高度，将当前柱子的索引入栈。

b. 如果当前柱子的高度小于栈顶柱子的高度，说明栈顶柱子的右边界已经确定，可以计算出以栈顶柱子为高度的最大矩形面积。具体计算方法是弹出栈顶柱子，并以它的高度为矩形的高，以当前柱子的索引减去弹出的柱子的索引减一为矩形的宽，计算面积并更新最大矩形面积。

c. 遍历完 heights 数组后，如果栈中还有柱子，按照 b 步骤中的方法依次弹出栈顶元素，并更新最大矩形面积。

下面是 C++ 的代码实现：

int largestRectangleArea(vector<int>& heights) {
    stack<int> st;
    heights.push_back(0); // 在数组末尾添加一个高度为 0 的柱子，方便计算最后一个柱子的面积
    int n = heights.size();
    int ans = 0;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && heights[i] < heights[st.top()]) {
            int h = heights[st.top()];
            st.pop();
            int w = st.empty() ? i : i - st.top() - 1;
            ans = max(ans, h * w);
        }
        st.push(i);
    }
    return ans;
}

其中，heights 为输入的柱状图，返回值为最大矩形面积。