当前位置:

首页 > 编程开发 > 如何通过数组实现单调栈结构实战解决搜索最近更大变量元素的性能

如何通过数组实现单调栈结构实战解决搜索最近更大变量元素的性能

使用数组实现单调栈可高效解决搜索最近更大元素问题,时间复杂度与空间复杂度均为O(n)。手动预分配数组大小,用整数指针控制栈顶,避免扩容开销与对象封装,提升性能。核心思路是维护单调递减栈,一次遍历完成所有查询并记录结果。

本文目录

    数组实现单调栈,解决“搜索最近更大元素”这一经典问题,可以说是又快又省内存。核心思路其实很简单——手动维护一个严格递减(或递增)的数组栈,通过一次遍历就能完成所有查询,时间复杂度稳稳地落在O(n),空间复杂度也是O(n)。

    为什么数组比链表或Stack类更值得选择?

    Ja va的Stack类基于Vector,自带线程同步,慢;Python的list虽然能当栈用,但频繁的append/pop背后总免不了动态扩容和边界检查。而手动用数组模拟栈,好处很明显:

    • 预分配固定大小(比如输入数组的长度),彻底避开扩容开销
    • 用一个整数指针top控制栈顶,所有读写操作就是一次O(1)的数组索引访问
    • 没有对象封装,没有方法调用,CPU缓存命中率自然更高

    数组单调栈的核心逻辑——以“下一个更大元素”为例

    目标很明确:对每个位置i,找出它右边第一个比它大的元素。做法是维护一个单调递减栈——栈里存的是索引,对应值从底到顶递减。流程是这样的:

    • 遍历数组,当前索引记为i
    • 如果栈非空,并且nums[i] > nums[stack[top]],说明i就是栈顶索引的“下一个更大位置”,弹出栈顶并记录结果
    • 重复上一步,直到不满足条件或栈为空,再把i压入栈
    • 遍历结束后,栈里剩下的索引都没有更大元素了,按需要设为-1或null

    手写数组栈的关键代码结构(Ja va示例)

    咱们直接看一段Ja va示例代码,完全不依赖任何集合类,纯数组加一个top指针就行:

    int[] stack = new int[nums.length]; // 预分配空间
    int top = -1;                        // 栈顶索引,-1表示空栈
    int[] res = new int[nums.length];
    Arrays.fill(res, -1);                // 默认没有更大元素
    
    for (int i = 0; i < nums.length; i++) {
        while (top >= 0 && nums[i] > nums[stack[top]]) {
            int idx = stack[top--];
            res[idx] = nums[i]; // 或者存下标,根据题意定
        }
        stack[++top] = i;
    }

    这里有个小细节需要注意:top初始化为-1,++top是先自增再存,top--是先取再自减,完全符合栈的后进先出行为。

    实战中值得关注的优化点

    • 把while (top >= 0 && ...)换成while (top != -1 && ...),部分JVM对后者优化更友好
    • 将nums[stack[top]]提前读进局部变量,减少两次数组寻址的开销
    • 如果只需要下标而不需要具体值,可以省去res数组的初始化填充,等全部遍历完再统一处理残留结果
    • 对于超大数组(比如10⁷级别),如果索引范围不超过65536,可以考虑用short[]来存索引,内存带宽能省下一半
    本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系bd@zhengruan.com
    作者最新文章
    编程开发
    相关文章 更多
    Python如何实现带有撤销功能的栈_基于两个列表模拟操作历史
    Python如何实现带有撤销功能的栈_基于两个列表模拟操作历史

    用两个列表分别存储当前数据与操作日志,通过反向执行逆操作实现撤销,可避免内存浪费。撤销后执行新操作需清空未来历史,且逆操作中不可复用公开的push/pop方法,防止循环记录。空栈时pop或undo应静默失败。

    C#怎么使用stackalloc分配_C#栈上内存分配优化方法教程【高级】
    C#怎么使用stackalloc分配_C#栈上内存分配优化方法教程【高级】

    stackalloc是C#底层性能工具,必须配合Span使用,适用于零分配、短生命周期、固定大小连续内存场景。分配大小受线程栈限制,建议不超过64KB,超限会导致进程终止的StackOverflowException。不能跨async/await边界或存入字段,安全使用可提升热点路径吞吐3~5倍并降低GC压力。

    C++如何获取并打印函数的调用地址偏移 _ 符号化堆栈信息技巧【进阶】
    C++如何获取并打印函数的调用地址偏移 _ 符号化堆栈信息技巧【进阶】

    在C++调试中,获取函数调用地址偏移需用返回地址减去函数起始地址。Linux下利用backtrace()与dladdr()计算偏移;Windows中SymFromAddr()返回的起始地址需加模块基址;离线解析addr2line需先减去模块基址。偏移计算必须区分返回地址与函数入口,避免符号化失败。

    C++实现字符串中括号匹配算法 _ 栈结构在表达式解析的应用【详解】
    C++实现字符串中括号匹配算法 _ 栈结构在表达式解析的应用【详解】

    直截了当地说:用 std::stack 是最稳妥的选择,但必须处理好三类边界情况——空栈弹出、类型错配、遍历结束后栈非空;但凡漏掉一个,都会导致误判。这是括号匹配算法的核心共识,很多初学 C++ 的人在这上面栽过跟头。 为什么不能只靠 if (c == ')') 判断右括号? 仅仅比较字符是否相等?

    C++实现高性能并发无锁栈Lock-Free Stack _ CAS原子操作实战【源码】
    C++实现高性能并发无锁栈Lock-Free Stack _ CAS原子操作实战【源码】

    无锁栈实现需解决ABA问题,核心是通过版本号机制将指针与计数器打包为128位数据进行CAS操作。push和pop必须正确设置next指针及内存序,节点分配建议使用线程局部内存池,延迟释放需采用hazardpointer或EBR技术。验证是否真正无锁需检查底层原子操作是否为lock-free,并通过破坏性测试及工具检测数据竞争。

    Next.js + PostgreSQL + Prisma 全栈项目架构设计
    Next.js + PostgreSQL + Prisma 全栈项目架构设计

    基于Next.js、PostgreSQL和Prisma的全栈项目架构,核心包括垂直切片目录结构、PrismaSchema严格建模、按执行上下文区分数据获取策略(服务器组件直接查库、客户端组件走API路由)、环境变量隔离部署,以及通过Zod运行时校验、事务包裹和分级异常处理实现类型安全与纵深防御。

    Go 语言中 runtime.Stack 追踪 Goroutine 堆栈
    Go 语言中 runtime.Stack 追踪 Goroutine 堆栈

    runtime.Stack默认仅捕获当前goroutine堆栈,4KB缓冲区易导致截断。需设置大缓冲区并将第二个参数设为true才能获取所有goroutine堆栈。死锁诊断中可安全使用,但高并发频繁调用会导致停顿。无法直接获取指定goroutine堆栈,需借助内部调用或调试工具。

    Linux怎么查看进程消耗的堆栈内存 Linux下gdb分析进程详解
    Linux怎么查看进程消耗的堆栈内存 Linux下gdb分析进程详解

    在排查Linux进程内存问题时,我们常常关注堆内存,但栈内存的异常同样不容忽视。一个递归函数失控,或者一个大型局部数组,都可能悄无声息地耗尽栈空间,导致进程崩溃。那么,如何准确查看进程消耗的栈内存呢? 直接查看 /proc/[pid]/status 中的 VmStk 字段 最直接的方法,是查看内核为

    怎么通过分析 JVM 逃逸分析(Escape Analysis)理解为何局部对象可以在栈上分配
    怎么通过分析 JVM 逃逸分析(Escape Analysis)理解为何局部对象可以在栈上分配

    逃逸分析是JIT编译时的动态推断,用于判断对象是否可能被外部访问。只有确认对象无逃逸时,JIT才会进行标量替换等优化,将对象字段拆解为局部变量。优化需满足代码为热点且对象完全不逃逸,可通过编译日志与GC行为验证。编写代码时应避免对象逃逸,以自然获得JIT优化。

    如何在 Java 中利用 ArrayDeque 作为双端队列同时实现栈与队列的高效操作
    如何在 Java 中利用 ArrayDeque 作为双端队列同时实现栈与队列的高效操作

    ArrayDeque是基于循环数组的高效双端队列,支持O(1)时间复杂度的两端操作。模拟栈时应固定使用尾端方法(如push/pop),模拟队列则采用尾进头出策略(如offer/poll)。其性能优于传统Stack与LinkedList,是单线程环境下栈与队列的理想实现。

    查看更多
    精品专题 更多
    装机必备
    装机必备

    正软商城装机必备专区,精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件,帮助用户快速完成新电脑软件配置。

    Windows
    Windows

    正软商城Windows软件专区,汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件,提供软件介绍、系统要求、正版授权及购买下载服务。

    PDF教程
    PDF教程

    正软商城PDF教程频道提供PDF编辑、转换、合并、拆分、压缩及格式处理方法,同时介绍常用PDF软件和工具的使用技巧。

    Mac软件 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    Aperty macOS版
    Aperty macOS版
    macOS

    Aperty 是 Skylum 推出的 AI 人像修图软件,支持自然肤质修饰、瑕疵处理、面部与身体调整、预设及批量同步。

    WINDOWS 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    PixTV 网页版
    PixTV 网页版
    Windows

    PixTV 是一款在浏览器中使用的 AI 视觉内容创作平台,提供图片、视频、音频、文字生成、AI 分镜、局部重绘、提示词反推和无限画布等工具,适合短剧、漫剧、广告及社交媒体内容制作。