题目

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

img

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

img

输入： heights = [2,4]
输出： 4

提示：

  • 1 <= heights.length <=105
  • 0 <= heights[i] <= 104

解答

解题思路：

  1. 遍历给定的柱状图高度数组 heights，依次处理每个柱子。
  2. 使用一个栈来保存递增序列的索引。栈中的索引对应的柱子高度是递增的。
  3. 对于每个柱子，如果当前高度小于栈顶元素对应的高度，说明找到了栈顶元素的右边界。
  4. 弹出栈顶元素，并计算以栈顶元素为高度的矩形的面积。面积的宽度可以通过当前索引和新的栈顶元素索引之间的距离计算得到。
  5. 更新最大面积值。
  6. 将当前索引入栈，继续下一个柱子的处理。
  7. 遍历完所有柱子后，栈中剩余的索引对应的柱子高度没有右边界，因此以这些柱子高度计算的矩形面积可以直接得到。
  8. 返回最大面积值。
#include <stack>
#include <vector>
using namespace std;

int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();
    stack<int> st; // 使用栈来保存递增序列的索引
    int maxArea = 0;

    for (int i = 0; i <= n; i++) {
        // 如果当前高度小于栈顶元素对应的高度，说明找到了栈顶元素的右边界
        // 计算以栈顶元素为高度的矩形的面积，并更新最大面积
        while (!st.empty() && (i == n || heights[i] < heights[st.top()])) {
            int h = heights[st.top()];
            st.pop();
            int w = st.empty() ? i : (i - st.top() - 1);
            maxArea = max(maxArea, h * w);
        }

        // 将当前索引入栈
        st.push(i);
    }

    return maxArea;
}

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