#P4082. 柱状图中最大的矩形
-
ID: 2323
Tried: 28
Accepted: 14
Difficulty: 8
-
算法标签>数据结构栈
柱状图中最大的矩形
题目内容
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为1。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
输入描述
输入n个非负整数
输出描述
输出一个整数表示矩形最大面积
样例1
输入
2 1 5 6 2 3
输出
10
说明
最大的矩形为图中红色区域，面积为 10
样例2
输入
2 4
输出
4
说明
提示：
- 1<=heights.length<=105
- 0<=heights[i]<=104
题解
题面描述
给定 n 个非负整数，表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度均为 1。要求计算在该柱状图中能够勾勒出来的矩形的最大面积。
思路
我们使用单调栈来解决这道题。主要思路如下：
- 单调递增栈：
用一个栈来存储柱子的下标，使得栈中对应的高度是单调递增的。 - 遇到较低柱子时弹栈计算面积：
当遇到一个柱子的高度小于栈顶柱子的高度时，从栈中弹出栈顶元素，此时以被弹出的柱子为最低高度，计算以它为高度的矩形面积。矩形的宽度为当前下标与新栈顶下标的差值减一。 - 最后处理栈中剩余柱子：
最后将栈中剩余的柱子逐个弹出，同样计算面积，此时宽度为 n 与当前栈中元素的差值。 - 时间复杂度：
每个柱子最多入栈和出栈一次，总时间复杂度为 O(n)。
代码分析
- 数据结构： 使用栈存储柱子的下标；数组存储柱子的高度。
- 公式说明：
当弹出栈顶下标 i 后，如果栈为空，则宽度为当前下标 j；如果栈不为空，则宽度为 j−stack.top()−1。
面积计算公式为：area=heights[i]×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);
}
}