题目描述
定义栈的数据结构, 请在该类型中实现一个能够得到栈中所含最小元素的 min 函数 (时间复杂度应为 O(1)).
思路: 用到两个栈: 一个栈 1 全部压, 一个栈 2 压入一个元素后, 之后压的元素只能比之前的小于或者等于, 这样一来最小的就是在栈 2 的栈顶, 出栈的时候只有当栈 1 的栈顶元素和栈 2 的栈顶元素相同时, 此时栈 2 出栈, 最小的还是栈 2 的栈顶元素.
c++ 代码如下:
- class Solution {
- public:
- stack<int> stack1,stack2;
- void push(int value) {
- stack1.push(value);
- if(stack2.empty())
- stack2.push(value);
- else if(value<=stack2.top())
- {
- stack2.push(value);
- }
- }
- void pop() {
- if(stack1.top()==stack2.top())
- stack2.pop();
- stack1.pop();
- }
- int top() {
- return stack1.top();
- }
- int min() {
- return stack2.top();
- }
- };
来源: http://www.bubuko.com/infodetail-3133018.html