题解

题面描述

给定 $n$ 个非负整数，表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度均为 $1$。要求计算在该柱状图中能够勾勒出来的矩形的最大面积。

思路

我们使用单调栈来解决这道题。主要思路如下：

1. 单调递增栈：
   用一个栈来存储柱子的下标，使得栈中对应的高度是单调递增的。
2. 遇到较低柱子时弹栈计算面积：
   当遇到一个柱子的高度小于栈顶柱子的高度时，从栈中弹出栈顶元素，此时以被弹出的柱子为最低高度，计算以它为高度的矩形面积。矩形的宽度为当前下标与新栈顶下标的差值减一。
3. 最后处理栈中剩余柱子：
   最后将栈中剩余的柱子逐个弹出，同样计算面积，此时宽度为 $n$ 与当前栈中元素的差值。
4. 时间复杂度：
   每个柱子最多入栈和出栈一次，总时间复杂度为 $O(n)$。

代码分析

• 数据结构： 使用栈存储柱子的下标；数组存储柱子的高度。
• 公式说明：
  当弹出栈顶下标 $i$ 后，如果栈为空，则宽度为当前下标 $j$；如果栈不为空，则宽度为 $j - stack.top() - 1$。
  面积计算公式为：$area = heights[i] \times width$
• 问题本质：
  本题关键在于利用单调栈快速确定以某一柱子为最低高度时，能够扩展的最大宽度，从而计算出矩形面积，遍历过程中不断更新最大面积。

C++

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

class Solution {
public:
    // 计算最大矩形面积
    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() && heights[i] < heights[st.top()]) {
                int h = heights[st.top()];
                st.pop();
                int width = st.empty() ? i : i - st.top() - 1;
                maxArea = max(maxArea, h * width);
            }
            st.push(i);
        }
        // 处理栈中剩余的柱子
        while (!st.empty()) {
            int h = heights[st.top()];
            st.pop();
            int width = st.empty() ? n : n - st.top() - 1;
            maxArea = max(maxArea, h * width);
        }
        return maxArea;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string inputLine;
    getline(cin, inputLine);
    istringstream iss(inputLine);
    vector<int> heights;
    int num;
    // 读取所有输入的整数
    while (iss >> num) {
        heights.push_back(num);
    }
    Solution solution;
    int result = solution.largestRectangleArea(heights);
    cout << result << "\n";
    return 0;
}

Python

class Solution:
    # 计算最大矩形面积
    def largestRectangleArea(self, heights: list) -> int:
        n = len(heights)
        stack = []
        max_area = 0
        for i in range(n):
            # 当当前柱子的高度小于栈顶柱子高度时，计算面积
            while stack and heights[i] < heights[stack[-1]]:
                h = heights[stack.pop()]
                width = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, h * width)
            stack.append(i)
        # 处理栈中剩余柱子
        while stack:
            h = heights[stack.pop()]
            width = n if not stack else n - stack[-1] - 1
            max_area = max(max_area, h * width)
        return max_area

if __name__ == "__main__":
    import sys
    # 读取输入数据，支持空格分隔
    data = sys.stdin.read().strip().split()
    # 将输入数据转换为整数列表
    heights = list(map(int, data))
    solution = Solution()
    result = solution.largestRectangleArea(heights)
    print(result)

Java

import java.util.*;
import java.io.*;

public class Main {
    static class Solution {
        // 计算最大矩形面积
        public int largestRectangleArea(int[] heights) {
            int n = heights.length;
            Stack<Integer> stack = new Stack<>();
            int maxArea = 0;
            for (int i = 0; i < n; i++) {
                // 当当前柱子的高度小于栈顶柱子高度时，计算面积
                while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
                    int h = heights[stack.pop()];
                    int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                    maxArea = Math.max(maxArea, h * width);
                }
                stack.push(i);
            }
            // 处理栈中剩余柱子
            while (!stack.isEmpty()) {
                int h = heights[stack.pop()];
                int width = stack.isEmpty() ? n : n - stack.peek() - 1;
                maxArea = Math.max(maxArea, h * width);
            }
            return maxArea;
        }
    }
    
    public static void main(String[] args) throws IOException {
        // 使用 BufferedReader 实现 ACM 模式下的输入输出
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        String[] parts = line.trim().split("\\s+");
        int[] heights = new int[parts.length];
        for (int i = 0; i < parts.length; i++) {
            heights[i] = Integer.parseInt(parts[i]);
        }
        Solution solution = new Solution();
        int result = solution.largestRectangleArea(heights);
        System.out.println(result);
    }
}

Leetcode 73.柱状图中最大的矩形-原题链接

题目内容

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

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

输入描述

输入$n$个非负整数

输出描述

输出一个整数表示矩形最大面积

样例1

输入

2 1 5 6 2 3

输出

10

说明

最大的矩形为图中红色区域，面积为 $10$

样例2

输入

2 4

输出

4

说明

提示：

• $1 <= heights.length <=10^5$
• $0 <= heights[i] <= 10^4$