python算法与数据结构---单调栈与实践

这篇具有很好参考价值的文章主要介绍了python算法与数据结构---单调栈与实践。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

单调栈

  • 单调栈是一个栈,里面的元素的大小按照它们所在栈的位置,满足一定的单调性;

  • 性质:

    • 单调递减栈能找到左边第一个比当前元素大的元素
    • 单调递增栈能找到左边第一个比当前元素小的元素
  • 应用场景

    • 一般用于解决第一个大于XXX或者第一个小于XXX这一类的题目
  • 优点:实践复杂度是线性的,每个元素只遍历一次
    python算法与数据结构---单调栈与实践,python学习及算法数据结构(结合力扣刷题),python,算法,数据结构

  • 单调递减栈,每次都能找到左边第一个比它大的数

  • 单调递增栈,每次都能找到左边第一个比它小的数

python算法与数据结构---单调栈与实践,python学习及算法数据结构(结合力扣刷题),python,算法,数据结构

84. 柱状图中最大的矩形

https://leetcode.cn/problems/largest-rectangle-in-histogram/description/
python算法与数据结构---单调栈与实践,python学习及算法数据结构(结合力扣刷题),python,算法,数据结构

解法一:暴力解法

依次遍历柱形的高度,对于每一个高度分别向两边扩散,求出当前高度为矩形的最大宽度

  • 向左遍历,看最多能向左延伸多长,找到大于等于当前柱形高度的最左边元素的下标;
  • 向右遍历,看最多能向右延伸多长,找到大于等于当前柱形高度的最右边元素的下标;
  • 计算当前高度对应的最大面积,与历史最大值进行比较并更新。

该解法在用例数量过多时,容易超出实时间限制

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        size = len(heights)
        res = 0
        for i in range(size):
            # 找左边最后一个大于等于heights[i]的下标
            left = i
            cur_height = heights[i]
            while left > 0 and heights[left-1] >= cur_height:
                left -= 1
            
            # 找右边最后一个大于等于heights[i]的下标
            right = i
            while right < size-1 and heights[right + 1] >= cur_height:
                right += 1
            
            max_width = right - left + 1
            res = 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] = -1
            else:
                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算法与数据结构---单调栈与实践,python学习及算法数据结构(结合力扣刷题),python,算法,数据结构

附录基础

python数据结构与算法理论基础(专栏)

数据结构与算法(python)

程序 = 数据结构 + 算法;而且在面试过程中这些是必考,必问的内容。内容大纲:基础数据结构(树、链表、栈、队列等)、常见算法(排序算法、递归算法等)。

专栏是基于python的基础知识,是很好的入门学习资料。帮助大家快速理解这些数据结构和常见算法的概念,同时结合力扣题目,也能更好的掌握这些知识,达到在面试中游刃有余的效果。

python基础语法

python基础精讲

本专栏主要针对python基础语法,帮助学习者快速接触并掌握python大部分最重要的语法特征。
1、基本数据类型和变量
2、分支结构与循环结构
3、函数与异常处理
4、类与模块
5、文件读写

通过本专栏可以快速掌握python的基础语法。文章来源地址https://www.toymoban.com/news/detail-812515.html

到了这里,关于python算法与数据结构---单调栈与实践的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 青岛大学_王卓老师【数据结构与算法】Week05_11_栈与递归_学习笔记

    本文是个人学习笔记,素材来自青岛大学王卓老师的教学视频。 一方面用于学习记录与分享, 另一方面是想让更多的人看到这么好的《数据结构与算法》的学习视频。 如有侵权,请留言作删文处理。 课程视频链接: 数据结构与算法基础–第05周11–3.4栈和递归 递归的定义

    2024年02月16日
    浏览(21)
  • 【数据结构】栈与队列

    栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端称为栈顶,另一端称为栈底 。栈中的数据元素遵守后进先出 LIFO (Last In First Out) 的原则。 压栈:栈的插入操作叫做进栈/压栈/入栈, 入数据在栈顶 。 出栈:栈的删除操

    2024年02月13日
    浏览(20)
  • 数据结构——栈与队列

    目录 一、栈 1.栈的定义  2.栈的分类与基本操作 1. 顺序栈 2.链栈 3.栈与递归的实现 1.递归的简单描述 2.递归过程及与栈的关联 3.递归过程示意图 二.队列 1.队列的定义  2.队列的分类与基本操作 1.顺序队列 2.链队列 3.循环队列 1.假溢出  2.循环队列 3.循环队列相关操作实现:

    2024年02月04日
    浏览(23)
  • 【数据结构】 栈与队列的相互实现

    队列与栈的操作算法是笔试面试中较为常见的题目。 本文将着重介绍平时面试中常见的关于队列与栈的应用题目,马上要进行秋招了。希望对你们有帮助 _😀 请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。 实现

    2024年02月10日
    浏览(22)
  • 数据结构之栈与队列详解

    栈和队列是一种特殊的线性结构,他与之前学的线性结构不同,栈和队列是拥有一种特殊规则的线性结构,虽然它是用数组或者链表实现,但是只有符合这种规则才能被称作栈或者队列 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和

    2024年01月16日
    浏览(21)
  • 【数据结构】栈与队列经典oj题

    🚀write in front🚀 📜所属专栏:初阶数据结构 🛰️博客主页:睿睿的博客主页 🛰️代码仓库:🎉VS2022_C语言仓库 🎡您的点赞、关注、收藏、评论,是对我最大的激励和支持!!! 关注我,关注我,关注我 , 你们将会看到更多的优质内容!!   栈两种线性表示都能实现

    2024年02月03日
    浏览(17)
  • 数据结构例题代码及其讲解-栈与队列

    栈Stack 后进先出 ​ 栈的结构体定义及基本操作。 初始化 ​ 这里初始化时是将栈顶指针指向-1,有些则是指向0,因此后续入栈出栈的代码略微有点区别 判断栈是否为空 压栈操作 由于初始时栈顶指针指向-1,因此需要先变化栈顶指针,然后入栈操作; 且当MaxSize为50时候,数

    2024年02月10日
    浏览(19)
  • 【数据结构】栈与队列经典选择题

    🚀write in front🚀 📜所属专栏: 🛰️博客主页:睿睿的博客主页 🛰️代码仓库:🎉VS2022_C语言仓库 🎡您的点赞、关注、收藏、评论,是对我最大的激励和支持!!! 关注我,关注我,关注我 , 你们将会看到更多的优质内容!!   在前面的学习中外面学习了栈与队列。

    2023年04月23日
    浏览(21)
  • 数据结构基础内容-----第四章 栈与队列

    栈(Stack)是计算机科学中的一种抽象数据类型,它是一个只能在一端进行插入和删除操作的线性数据结构。栈按照后进先出(LIFO)的原则存储数据,即最后放入的元素最先被取出。类比物理世界中的堆叠物品,每次加入的物品都被放在上面,取出时也只能从上面取出,最后

    2024年02月07日
    浏览(22)
  • (详解)数据结构-----------栈与队列 c语言实现

    本章将会详细讲解以下知识点: 目录 一:栈         1:栈的定义,栈的特点         2:用什么结构来实现栈与原因的分析?         3:  (超详解)栈的常用接口并且附上测试用例 二:队列         1:队列的定义,队列的特点         2:用什么结构来实现队列与原因的分析

    2024年02月11日
    浏览(19)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包