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

2024-01-10 15:58:55

84. 柱状图中最大的矩形

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

示例 1:
[图片]
输入:heights = [2,1,5,6,2,3]
输出:10
解释:最大的矩形为图中红色区域,面积为 10
示例 2:
[图片]
输入: heights = [2,4]
输出: 4

提示:

  • 1 <= heights.length <=10(5)
  • 0 <= heights[i] <= 10(4)

思路

    1. 接雨水 (opens new window)是找每个柱子左右两边第一个大于该柱子高度的柱子,而本题是找每个柱子左右两边第一个小于该柱子的柱子。
      这里就涉及到了单调栈很重要的性质,就是单调栈里的顺序,是从小到大还是从大到小。
  1. 在题解接雨水 (opens new window)中我讲解了接雨水的单调栈从栈头(元素从栈头弹出)到栈底的顺序应该是从小到大的顺序。
    那么因为本题是要找每个柱子左右两边第一个小于该柱子的柱子,所以从栈头(元素从栈头弹出)到栈底的顺序应该是从大到小的顺序!

文章来源:https://blog.csdn.net/qq_41735944/article/details/135502051
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。