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

题目描述

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

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

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

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

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

思路灵感图

主要代码

1. - (void)pushid)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.    }

10.    else

11.    {

12.    //2

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

14.        //3

15.        NSNumber *minObj;

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

17.  

18.        if (r == NSOrderedAscending)

19.        {

20.            minObj = [_stack peek];

21.  

22.        }

23.        else if(r == NSOrderedSame)

24.        {

25.            minObj = [_minStack peek];

26.  

27.        }

28.        else if(r == NSOrderedDescending)

29.        {

30.            minObj = [_minStack peek];

31.        }

32.  

33.        [_minStack push:minObj];

34.  

35.    }

36. }

代码思路解释

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

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

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

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

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

交流群昵称：ios-Swift/Object C开发上架
交流群号： 869685378   找ios马甲包开发者合作，有兴趣请添加Q 51259559

• 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