当前位置: 首页 > 科技观察

如何在O(1)中找到实时序列的最小值?

时间:2023-03-17 15:08:01 科技观察

最小栈最小栈可以在O(1)内找到栈中序列的最小值,所以这个特性常被用来提高算法性能。让我们看一下它的一个实现。分析过程栈分析:将元素推入mainstack,只有当当前元素小于tmpstack栈顶元素(实际上在mainstack中存储为元素索引)时,才推入tmpstack,索引为推入堆栈。假设mainstack当前有n个元素,那么tmpstack中至多有n??个元素。当等于n时,说明原堆叠序列为单调递减序列。出栈分析:元素从mainstack中出栈,但要注意出栈元素的index是否等于tmpstack栈顶,如果需要pop出tmpstack栈顶元素。可以预见,栈顶索引一定小于或等于出栈元素的索引(在mainstack栈中)。这道题需要注意两点:临时栈是主栈的元素索引入栈。如果临时栈为空,需要在主栈索引代码中先压入这个元素推送元素:defpush(self,val):""":typeval:int:rtype:None"""self.mainstack.append(val)ifnotself.tmpstack:self.tmpstack.append(len(self.mainstack)-1)#smallerthantopoftmpstackifself.mainstack[self.tmpstack[-1]]>val:self.tmpstack.append(len(self.mainstack)-1)后栈元素:defpop(self):""":rtype:None""“#minvaloftmpstackequalstopofmainstackifself.tmpstackandself.tmpstack[-1]==len(self.mainstack)-1:self.tmpstack.pop()returnsself。mainstack.pop()deftop(self):""":rtype:int"""ifself.mainstack:returnsself.mainstack[-1]使用tmpstack辅助栈换取O(1)查询最小复杂度defgetMin(self):""":rtype:int"""ifself.tmpstack:returnsself.mainstack[self.tmpstack[-1]]