• 代码随想录算法训练营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分钟

  • 相关阅读:
    【Pytorch】Pytorch学习笔记02 - 单变量时间序列 LSTM
    CAD中的超级修剪功能、使用CAD旋转命令绘制图形
    UDP和TCP的区别
    CorelDRAW Graphics Suite2024完整版最新功能介绍
    从哪里下载 Oracle database 11g 软件
    Linux 基础 + Web 部署
    QT 如何防止 QTextEdit 自动滚动到最下方
    数字化时代的探索，企业如何做好数字化转型？
    安卓主板MT8390(Genio 700)_MTK联发科Linux开发板方案
    App移动端测试（1）—— Android sdk部署
  • 原文地址：https://blog.csdn.net/u013003382/article/details/133191094