• 代码随想录算法训练营19期第60天

    84.柱状图中最大的矩形

    代码随想录

    初步思路：接雨水

    总结：

    • 接雨水那道题是找每个柱子左右两边第一个大于该柱子高度的柱子，所以单调栈从栈头（元素从栈头弹出）到栈底的顺序应该是从小到大的顺序。
    • 本题是找每个柱子左右两边第一个小于该柱子的柱子，所以单调栈从栈头（元素从栈头弹出）到栈底的顺序应该是从大到小的顺序。
    • 输入数组首尾各补上一个0（与接雨水不同的是，本题原首尾的两个柱子可以作为核心柱进行最大面积尝试）

       

    1. def largestRectangleArea(self, heights: List[int]) -> int:
    2.  
    3.         '''
    5.         找每个柱子左右侧的第一个高度值小于该柱子的柱子
    7.         单调栈：栈顶到栈底：从大到小（每插入一个新的小数值时，都要弹出先前的大数值）
    9.         栈顶，栈顶的下一个元素，即将入栈的元素：这三个元素组成了最大面积的高度和宽度
    11.         情况一：当前遍历的元素heights[i]大于栈顶元素的情况
    13.         情况二：当前遍历的元素heights[i]等于栈顶元素的情况
    15.         情况三：当前遍历的元素heights[i]小于栈顶元素的情况
    17.         '''
    18.  
    19.         heights.insert(0, 0)
    20.  
    21.         heights.append(0)
    22.  
    23.         stack = [0]
    24.  
    25.         result = 0
    26.  
    27.         for i in range(1, len(heights)):
    28.  
    29.             # 情况一
    30.  
    31.             if heights[i] > heights[stack[-1]]:
    32.  
    33.                 stack.append(i)
    34.  
    35.             # 情况二
    36.  
    37.             elif heights[i] == heights[stack[-1]]:
    38.  
    39.                 stack.pop()
    40.  
    41.                 stack.append(i)
    42.  
    43.             # 情况三
    44.  
    45.             else:
    46.  
    47.                 # 抛出所有较高的柱子
    48.  
    49.                 while stack and heights[i] < heights[stack[-1]]:
    50.  
    51.                     # 栈顶就是中间的柱子，主心骨
    52.  
    53.                     mid_index = stack[-1]
    54.  
    55.                     stack.pop()
    56.  
    57.                     if stack:
    58.  
    59.                         left_index = stack[-1]
    60.  
    61.                         right_index = i
    62.  
    63.                         width = right_index - left_index - 1
    64.  
    65.                         height = heights[mid_index]
    66.  
    67.                         result = max(result, width * height)
    68.  
    69.                 stack.append(i)
    70.  
    71.         return result

    用时：60分钟

  • 相关阅读:
    学习笔记 | 音视频 | 推流项目框架及细节
    JWT的登录认证与自校验原理分析
    7-2 摘花生
    ETLCloud制造业轻量级数据中台解决方案
    2017 黑马 C++ 教学视频
    Endgame P.O.O
    自阿里 P8 爆出 1031 道 java 面试题后，我在 某直聘狂拿千份 Offer
    字节跳动八进八出，offer到手，发现项目不重要算法才最重要
    数据库调优：Mysql索引对group by 排序的影响
    【DesignMode】装饰者模式（Decorator pattern）
  • 原文地址：https://blog.csdn.net/u013003382/article/details/133191094