【刷题DAY60】84.md

发表于 | 分类于

84.柱状图中最大的矩形

题目链接：https://leetcode.cn/problems/largest-rectangle-in-histogram

0x1 看到题目的第一想法

0x2 自己实现过程中遇到哪些困难

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

  • 找每个柱子左右两边第一个小于该柱子的柱子
    • 双指针法
    • 单调栈
      • 头尾需要加0
      • 从栈底到栈顶保存从小到大的下标（严格递增）
      • 每插入一个新的小数值时，都要弹出先前的大数值
      • 栈顶：该柱子；即将要入栈：右边第一个矮于当前柱子的下标；栈顶的下一个元素：左边第一个矮于当前柱子的下标

0x5 今日收获，记录一下自己的学习时长

  • 1.5h

总结

  • 要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时就要想到可以用单调栈

复习

  • day39
    • 动态规划
      • 不同路径

待重点复习

84