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

题目描述

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

• push（x） - 将元素x推入堆栈。

• pop（） - 删除堆栈顶部的元素。

• top（） - 获取顶部元素。

• getMin（） - 检索堆栈中的最小元素。

思路灵感图

主要代码

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.        elseif(r ==NSOrderedSame)

21.        {

22.            minObj =[_minStack peek];

23.        }

24.        elseif(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