龙岗外贸网站建设公司,博览局网站建设,湖南如何做网络营销,网站备案复查单调栈 单调栈是一个栈#xff0c;里面的元素的大小按照它们所在栈的位置#xff0c;满足一定的单调性#xff1b; 性质#xff1a; 单调递减栈能找到左边第一个比当前元素大的元素#xff1b;单调递增栈能找到左边第一个比当前元素小的元素#xff1b; 应用场景 一般用…单调栈 单调栈是一个栈里面的元素的大小按照它们所在栈的位置满足一定的单调性 性质 单调递减栈能找到左边第一个比当前元素大的元素单调递增栈能找到左边第一个比当前元素小的元素 应用场景 一般用于解决第一个大于XXX或者第一个小于XXX这一类的题目 优点实践复杂度是线性的每个元素只遍历一次 单调递减栈每次都能找到左边第一个比它大的数 单调递增栈每次都能找到左边第一个比它小的数 84. 柱状图中最大的矩形
https://leetcode.cn/problems/largest-rectangle-in-histogram/description/
解法一暴力解法
依次遍历柱形的高度对于每一个高度分别向两边扩散求出当前高度为矩形的最大宽度
向左遍历看最多能向左延伸多长找到大于等于当前柱形高度的最左边元素的下标向右遍历看最多能向右延伸多长找到大于等于当前柱形高度的最右边元素的下标计算当前高度对应的最大面积与历史最大值进行比较并更新。
该解法在用例数量过多时容易超出实时间限制
class Solution:def largestRectangleArea(self, heights: List[int]) - int:size len(heights)res 0for i in range(size):# 找左边最后一个大于等于heights[i]的下标left icur_height heights[i]while left 0 and heights[left-1] cur_height:left - 1# 找右边最后一个大于等于heights[i]的下标right iwhile right size-1 and heights[right 1] cur_height:right 1max_width right - left 1res max(res, max_width * cur_height)return res解法二单调栈
获取每根柱子左边第一个比它低的柱子坐标单调递增栈获取每根柱子右边第一个比它低的柱子下标倒序来做就是左边第一个比它低的柱子遍历每根柱子求最大面积哨兵技巧两边各添加一个虚拟柱子
class Solution:def largestRectangleArea(self, heights: List[int]) - int:stack []left [0 for _ in range(len(heights))]right [0 for _ in range(len(heights))]res 0# 获取每根柱子左边第一个比它低的柱子下标for i in range(len(heights)):while stack and heights[stack[-1]] heights[i]:stack.pop()if not stack:left[i] -1else:left[i] stack[-1]stack.append(i)stack []# 获取每根柱子右边第一个比它低的柱子下标for j in range(len(heights) - 1, -1, -1):while stack and heights[stack[-1]] heights[j]:stack.pop()if not stack:right[j] len(heights)else:right[j] stack[-1]stack.append(j)# 求最大面积for i in range(len(heights)):res max(res, heights[i] * (right[i] - left[i] - 1))return res单调栈图示获取每根柱子右边第一个比它低的柱子下标则需要倒序来做
附录基础
python数据结构与算法理论基础专栏
数据结构与算法pythonhttp://t.csdnimg.cn/Gb6MN
程序 数据结构 算法而且在面试过程中这些是必考必问的内容。内容大纲基础数据结构树、链表、栈、队列等、常见算法排序算法、递归算法等。
专栏是基于python的基础知识是很好的入门学习资料。帮助大家快速理解这些数据结构和常见算法的概念同时结合力扣题目也能更好的掌握这些知识达到在面试中游刃有余的效果。
python基础语法
python基础精讲 http://t.csdnimg.cn/HdKdi
本专栏主要针对python基础语法帮助学习者快速接触并掌握python大部分最重要的语法特征。 1、基本数据类型和变量 2、分支结构与循环结构 3、函数与异常处理 4、类与模块 5、文件读写
通过本专栏可以快速掌握python的基础语法。
