欢迎关注
最酷最in的云资讯

100天iOS数据结构与算法实战 Day07 – 栈的算法实战 Min Stack


题目描述

设计一个栈支持push, pop, top,并且检索最小元素在恒定时间内。

  • push(x) – 将元素x推入堆栈。

  • pop() – 删除堆栈顶部的元素。

  • top() – 获取顶部元素。

  • getMin() – 检索堆栈中的最小元素。

思路灵感图

1304277-02a006bb98fbda4a.gif

主要代码

  1. - (void)push🙁id)object

  2. {

  3. //1

  4.    if ([_stack isEmpty])

  5.    {

  6.        [_stack push:[NSNumber numberWithInteger:[object integerValue]]];

  7.        [_minStack push:[NSNumber numberWithInteger:[object integerValue]]];


  8.    }

  9.    else

  10.    {

  11.    //2

  12.        [_stack push:[NSNumber numberWithInteger:[object integerValue]]];

  13.        //3

  14.        NSNumber *minObj;

  15.        NSComparisonResult r = [[_stack peek] compare:[_minStack peek]];


  16.        if (r == NSOrderedAscending)

  17.        {

  18.            minObj = [_stack peek];


  19.        }

  20.        else if(r == NSOrderedSame)

  21.        {

  22.            minObj = [_minStack peek];


  23.        }

  24.        else if(r == NSOrderedDescending)

  25.        {

  26.            minObj = [_minStack peek];

  27.        }


  28.        [_minStack push:minObj];


  29.    }

  30. }

代码思路解释

要求O (1)时间复杂度获取最小元素,我们借助一个辅助栈来实现。


1. 如果栈为空,则stack 和 minStack 都把这个元素进栈。

2. 如果栈不为空,则stack先吧这个元素进栈。

3. minStack的栈顶最小元素和这个元素对比,小于等于者进minStack。

总结:每次把最小者进minStack,这样minStack就是一个有序的栈,而栈顶元素就是最小元素,我们还可以根据这个思路实现找到最大元素。这个思路牺牲了空间。其实还有更好的办法,用O(1)时间和O(1)的额外辅助空间实现,这里就留给读者思考了。

GitHubDemo

GitHubDemo链接[1]  

References

[1] GithubDemo: 

https://github.com/renmoqiqi/100-Days-Of-iOS-DataStructure-Algorithm/tree/master/Day07

转载自公众号:人魔七七

  • 100天iOS数据结构与算法实战 Day01

  • 100天iOS数据结构与算法实战 Day02 – 栈

  • 100天iOS数据结构与算法实战 Day03 – 栈的算法实战 Valid Parentheses

  • 100天iOS数据结构与算法实战 Day04 – 栈的算法实战 逆波兰表示法

  • 100天iOS数据结构与算法实战 Day05 – 栈的算法实战 Evaluate Reverse Polish Nota

  • 100天iOS数据结构与算法实战 Day06 – 栈的算法实战 Simplify Path

赞(0) 打赏
未经允许不得转载:云微资讯 » 100天iOS数据结构与算法实战 Day07 – 栈的算法实战 Min Stack
分享到: 更多 (0)

云微资讯 科技新媒体资讯平台

关于我们联系我们

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

支付宝扫一扫打赏

微信扫一扫打赏