企业官网建设流程全解析

LeetCode 84. 柱状图中最大的矩形

📌 题目描述

题目级别：困难

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

• 示例 1:
  输入：heights = [2,1,5,6,2,3]
  输出：10
  解释：最大的矩形为高度为 5 和 6 的两根柱子组成的矩形，面积为5 * 2 = 10。

💡 破题思路：三次遍历寻找左右边界

要求出最大矩形，我们可以转换思维：以每一根柱子的高度为准，它向左向右最多能延伸多宽？
延伸的极限在哪里？就在于遇到了第一个比它矮的柱子！

所以，我们只需要利用单调递增栈：

1. 从左往右扫一遍，找到每个柱子左侧第一个比它矮的位置，存入l数组。
2. 从右往左扫一遍，找到每个柱子右侧第一个比它矮的位置，存入r数组。
3. 最后再遍历一次，以每个柱子为高，计算宽度r[i] - l[i] - 1，求出最大面积。

⚠️ 面试避坑点：
很多题解喜欢用int l[n], r[n]这种变长数组（VLA），这在严格的 C++ 标准下是会编译报错的。在大厂手撕代码时，遇到动态长度的数组，请务必使用vector<int>！

💻 C++ 代码实现 (规范版)

classSolution{public:intlargestRectangleArea(vector<int>&heights){intn=heights.size();stack<int>st;// 规范写法：使用 vector 而不是 VLAvector<int>l(n),r(n);// 1. 寻找左侧第一个比自己矮的柱子for(inti=0;i<n;i++){while(st.size()&&heights[st.top()]>=heights[i])st.pop();// 如果栈空了，说明左边没有比自己矮的，边界延展到极左 -1l[i]=st.empty()?-1:st.top();st.push(i);}// 清空栈，准备第二次遍历while(st.size())st.pop();// 2. 寻找右侧第一个比自己矮的柱子for(inti=n-1;i>=0;i--){while(st.size()&&heights[st.top()]>=heights[i])st.pop();// 如果栈空了，说明右边没有比自己矮的，边界延展到极右 nr[i]=st.empty()?n:st.top();st.push(i);}intres=0;// 3. 结算每一个柱子能勾勒的最大面积for(inti=0;i<n;i++){res=max(res,(r[i]-l[i]-1)*heights[i]);}returnres;}};