【力扣hot100】 84. 柱状图中最大的矩形

张开发
• 2026/4/19 17:57:49 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

【力扣hot100】 84. 柱状图中最大的矩形
一、题目给定 n 个非负整数用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1 。 求在该柱状图中能够勾勒出来的矩形的最大面积。 示例 1:输入heights [2,1,5,6,2,3] 输出10 解释最大的矩形为图中红色区域面积为 10 示例 2输入 heights [2,4] 输出 4 提示 1 heights.length 105 0 heights[i] 104二、思路第一眼就想到单调栈了但是一直卡在如何在不pop元素的情况下遍历栈中所有的成员。但后面发现在pop元素时结算即可。思路算是比较经典吧用栈来存储高度单调递减的下标当更小的元素进来时将栈里比他大的挨个pop出去并结算开区间的面积大小最后再把自身下标push下标进去。三、题解class Solution { public: int largestRectangleArea(vectorint heights) { int res0; stackint st; heights.push_back(0); for(int i0;iheights.size();i){ while(!st.empty()heights[i]heights[st.top()]){ int hst.top(); st.pop(); int leftst.empty()?-1:st.top(); int widthi-1-left; resmax(res,heights[h]*width); } st.push(i); } return res; } };

更多文章