最大矩形面积c++

以下是一个用C++实现的求最大矩形面积的算法：

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

using namespace std;

int largestRectangleArea(vector<int>& heights) {
    stack<int> stk;
    int maxArea = 0;
    int i = 0;
    
    while (i < heights.size()) {
        if (stk.empty() || heights[i] >= heights[stk.top()]) {
            stk.push(i);
            i++;
        }
        else {
            int top = stk.top();
            stk.pop();
            int area = heights[top] * (stk.empty() ? i : i - stk.top() - 1);
            maxArea = max(maxArea, area);
        }
    }
    
    while (!stk.empty()) {
        int top = stk.top();
        stk.pop();
        int area = heights[top] * (stk.empty() ? i : i - stk.top() - 1);
        maxArea = max(maxArea, area);
    }
    
    return maxArea;
}

int main() {
    vector<int> heights = {2, 1, 5, 6, 2, 3};
    int area = largestRectangleArea(heights);
    cout << "最大矩形面积为: " << area << endl;
    
    return 0;
}

这个算法的思路是使用一个栈来存储递增的高度序列的索引，当遇到一个比栈顶元素小的高度时，就将栈顶元素弹出，并计算以该高度为最低高度的矩形的面积。然后将当前元素的索引入栈，继续遍历数组。最后，如果栈不为空，就将栈中剩余元素依次弹出，并计算以这些高度为最低高度的矩形的面积。最大的面积即为所求的最大矩形面积