免费app下载网站,网站的功能与建设方案,品牌设计公司品牌设计公司排名,泰安房产信息网官网首页LeetCode-84. 柱状图中最大的矩形【栈 数组 单调栈】 题目描述#xff1a;解题思路一#xff1a;单调栈解题思路二#xff1a;解题思路三#xff1a; 题目描述#xff1a;
给定 n 个非负整数#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻#xff0c;且… LeetCode-84. 柱状图中最大的矩形【栈 数组 单调栈】 题目描述解题思路一单调栈解题思路二解题思路三 题目描述
给定 n 个非负整数用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1 。
求在该柱状图中能够勾勒出来的矩形的最大面积。
示例 1: 输入heights [2,1,5,6,2,3] 输出10 解释最大的矩形为图中红色区域面积为 10 示例 2 输入 heights [2,4] 输出 4
提示
1 heights.length 105 0 heights[i] 104
解题思路一单调栈
柱状图前后加0维护一个从栈底到栈顶的单调增栈。【栈顶大于前一个元素】那么获取到 主要就是分析清楚如下三种情况
情况一当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况【进栈】 情况二当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况【可忽略】 情况三当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况【计算当前ans(i - stack[-1] - 1) * heights[stack[-1]】
我在 height数组上后都加了一个元素0 为什么这么做呢
首先来说末尾为什么要加元素0
如果数组本身就是升序的例如[2,4,6,8]那么入栈之后 都是单调递减一直都没有走 情况三 计算结果的哪一步所以最后输出的就是0了。 如图 那么结尾加一个0就会让栈里的所有元素走到情况三的逻辑。
开头为什么要加元素0
如果数组本身是降序的例如 [8,6,4,2]在 8 入栈后6 开始与8 进行比较此时我们得到 mid8rigt6但是得不到 left。
mid、leftright 都是对应版本一里的逻辑
因为 将 8 弹出之后栈里没有元素了那么为了避免空栈取值直接跳过了计算结果的逻辑。
之后又将6 加入栈此时8已经弹出了然后 就是 4 与 栈口元素 8 进行比较周而复始那么计算的最后结果resutl就是0。 如图所示
class Solution:def largestRectangleArea(self, heights: List[int]) - int:heights.insert(0, 0)heights.append(0)stack [0]result 0for i in range(1, len(heights)):if heights[i] heights[stack[-1]]:stack.append(i)elif heights[i] heights[stack[-1]]:stack.pop()stack.append(i)else:while stack and heights[i] heights[stack[-1]]:mid_index stack[-1]stack.pop()if stack:w i - stack[-1] - 1result max(result, w * heights[mid_index])stack.append(i)return result时间复杂度O(n) 空间复杂度O(n)
解题思路二 时间复杂度O(n) 空间复杂度O(n)
解题思路三 时间复杂度O(n) 空间复杂度O(n)
