取堆栈最值

问题描述

设计一种数据结构，使得可以在O(1)的时间内取得最小值，同时要求PUSH和POP也是O(1)的时间复杂度。

方案：

从题目要求来说，应该是一种支持堆栈操作方式的数据结构。栈的压入可以统计到当前已经入栈的所有元素中最值。出栈时，前面弹出的元素不会影响后面元素弹出时的最小值。

因此可以使用辅助栈记录当前入栈的最小值。或者直接扩展栈元素内容。