100天iOS数据结构与算法实战 Day07 – 栈的算法实战 Min Stack
题目描述
设计一个栈支持push, pop, top,并且检索最小元素在恒定时间内。
-
push（x） – 将元素x推入堆栈。
-
pop（） – 删除堆栈顶部的元素。
-
top（） – 获取顶部元素。
-
getMin（） – 检索堆栈中的最小元素。
思路灵感图
主要代码
-
- (void)push:(id)object -
{ -
//1 -
if ([_stack isEmpty]) -
{ -
[_stack push:[NSNumber numberWithInteger:[object integerValue]]]; -
[_minStack push:[NSNumber numberWithInteger:[object integerValue]]]; -
} -
else -
{ -
//2 -
[_stack push:[NSNumber numberWithInteger:[object integerValue]]]; -
//3 -
NSNumber *minObj; -
NSComparisonResult r = [[_stack peek] compare:[_minStack peek]]; -
if (r == NSOrderedAscending) -
{ -
minObj = [_stack peek]; -
} -
else if(r == NSOrderedSame) -
{ -
minObj = [_minStack peek]; -
} -
else if(r == NSOrderedDescending) -
{ -
minObj = [_minStack peek]; -
} -
[_minStack push:minObj]; -
} -
}
代码思路解释
要求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
转载自公众号：人魔七七
About The Author
