leetcode:84.柱状图中最大的矩形

基础思路:

需要选出基准元素,选出左边第一个比它小的柱子,以及右边第一个比它小的柱子。

单调栈的应用:

当遍历到的元素小于栈顶元素时,栈顶元素是基准元素,遍历到的元素是右边第一个比它小的柱子,和栈顶相邻的栈内元素是左边第一个比它小的柱子。

面积求解:h是基准柱子的高,w是right-left-1。

首尾加0:首部加0是因为当原数组是单调递减的,为了确保栈顶元素弹出后栈内依然有元素,在数组首部进行加0;

尾部加0是因为当原数组是单调递增的,当数组内所有元素全部入栈,栈内元素满足单调递减,结果无法得出,尾部加0可以实现遍历到的元素小于栈顶元素,从而得出结果。

代码实现:

相关推荐

  1. LeetCode 84. 矩形

    2024-04-20 22:36:03       15 阅读

最近更新

  1. TCP协议是安全的吗?

    2024-04-20 22:36:03       18 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2024-04-20 22:36:03       19 阅读
  3. 【Python教程】压缩PDF文件大小

    2024-04-20 22:36:03       18 阅读
  4. 通过文章id递归查询所有评论(xml)

    2024-04-20 22:36:03       20 阅读

热门阅读

  1. Spring Cloud Gateway面试题

    2024-04-20 22:36:03       53 阅读
  2. Ubuntu如何给tar.gz文件创建桌面快捷方式

    2024-04-20 22:36:03       51 阅读
  3. 力扣经典150题第三十三题:最小覆盖子串

    2024-04-20 22:36:03       19 阅读
  4. 多数元素(C++)

    2024-04-20 22:36:03       13 阅读
  5. SpringMVC接收参数方式讲解

    2024-04-20 22:36:03       16 阅读