代码随想录算法训练营第六十天 | 84.柱状图中最大的矩形

标签：momoDescStack int 随想录 len heights 柱状图 矩形 84

 

 

---

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

 

---

func largestRectangleArea(heights []int) int { heights = append([]int{0}, heights...) heights = append(heights, 0) varmomoDescStack []int varresint fori := 0; i < len(heights); i++ { forlen(momoDescStack) != 0 && heights[momoDescStack[len(momoDescStack)-1]] > heights[i] { cur := momoDescStack[len(momoDescStack)-1] momoDescStack = momoDescStack[:len(momoDescStack)-1] iflen(momoDescStack) != 0 { res = max((i-momoDescStack[len(momoDescStack)-1]-1)*heights[cur], res) } } momoDescStack = append(momoDescStack, i) } return res }

标签：momoDescStack,int,随想录,len,heights,柱状图,矩形,84
From： https://www.cnblogs.com/suxinmian/p/18104363