栈的最大值问题——深入剖析

常数时间求栈的最大值


问题描述:

一个栈stack,具有push和pop操作,其时间复杂度皆为O(1)。
设计算法max操作,求栈中的最大值,该操作的时间复杂度也要求为O(1)。可以修改栈的存储方式,push,pop的操作,但是要保证O(1)的时间复杂度,空间时间复杂度无要求。

算法描述:
一个存储所有最大值的栈Sm。

  1. 当push入栈的元素大于当前最大元素,将该元素压入最大值栈Sm;
  2. Sm栈顶始终保存栈中当前的最大元素;
  3. 当前最大元素被pop出栈时,将Sm栈顶的对应最大元素也弹出栈。
    max操作即为获得Sm栈顶最大元素。

假设元素以5,4,1,2,3,10,9,8,6,7,15顺序入栈,则两个栈中存储的元素如下图所示:


常数时间空间求栈的最大值


问题描述:
一个整数栈stack,具有push和pop操作,其时间空间复杂度皆为O(1)。
设计算法max操作,求栈中的最大值,该操作的时间空间复杂度也要求为O(1)。可以修改栈的存储方式,push,pop的操作,但是要保证O(1)的时间空间复杂度。

算法描述:
变量Max保存当前最大元素值,初始值为最小整数m。

  1. 当push入栈时,将(当前元素-Max)存入栈中,
    若当前元素小于Max,栈中元素为负数;
    若当前元素大于等于Max,栈中元素为非负数,将Max替换为当前元素。

  2. 当pop出栈时,
    若栈中元素为负数,则将(栈中元素+Max)弹出栈;
    若栈中元素为非负数,则将Max弹出栈,并将Max替换为(Max-栈中元素)。

  3. Max即为当前栈中最大元素值。

主要思路是将最大值以某种方式在原有栈中标记出来,从而减少空间使用。可以用正负数来区分普通元素和最大值元素:
普通元素使用负数存储(元素-Max);
最大值元素使用非负数存储(New Max - Old Max);
这样便可在栈中区分普通元素和最大值元素,并可通过Max恢复Old Max。

假设元素以5,4,1,2,3,10,9,8,6,7,15顺序入栈,则两个栈中存储的元素如下图所示:

  1. 元素5,4,1,2,3入栈后的情况


  2. 元素10,9,8,6,7入栈后的情况


  3. 元素15入栈后的情况


  4. 元素15出栈时的情况


  5. 元素15出栈后的情况(恢复原有状态)


最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,779评论 0 33
  • 8086汇编 本笔记是笔者观看小甲鱼老师(鱼C论坛)《零基础入门学习汇编语言》系列视频的笔记,在此感谢他和像他一样...
    Gibbs基阅读 37,424评论 8 114
  • 136.泛型 泛型代码让你可以写出灵活,可重用的函数和类型,它们可以使用任何类型,受你定义的需求的约束。你可以写出...
    无沣阅读 1,528评论 0 4
  • 1. Java基础部分 基础部分的顺序:基本语法,类相关的语法,内部类的语法,继承相关的语法,异常的语法,线程的语...
    子非鱼_t_阅读 31,780评论 18 399
  • 十月,阴雨延绵围着厚毛毯坐在窗边,看雨滴从房檐流下来,一滴二滴……院子里杏树的叶子不似夏天时墨绿的压抑而是独属于秋...
    禾小酒阅读 262评论 1 1