如何在O(1)时间复杂度获取栈中最大值和最小值
Acx7 人气:0问题描述:
如何在O(1)时间复杂度获取栈中的最大值和最小值?
问题分析:
普通栈规定的push(入栈)、pop(出栈)、peek(查看栈顶)等操作都只能在栈顶上操作,如果栈中元素是有序的,那么我们就可以记录栈顶和栈底元素完成问题要求,但这是不可能的。普通栈不能解决问题,显然我们需要重新定义一种新的栈结构。能否在栈中定义两个变量min和max记录最小值和最大值呢,答案是否定的,因为并不是只有进栈操作,经过一系列出栈操作后,有可能最开始的最大值和最小值已经出栈。为了解决这个问题,我们就需要两个辅助栈记录栈的每个状态下的最大值和最小值。
算法描述:
定义一个minStack栈和一个maxStack栈,分别在栈顶保存当前栈内最小值和最大值,以minStack为例,每次有元素入栈,就与minStack的栈顶元素比较,若小于栈顶元素,则入栈成为新的栈顶元素,若大于栈顶元素,则入栈原先的栈顶元素,maxStack栈与上述思路相同。出栈时,三个栈都需要出栈。定义getMin与getMax函数分别返回minStack和maxStack栈顶元素,实现在O(1)时间复杂度获取栈中的最小值和最大值。
性能分析:
时间复杂度:O(1)
空间复杂度:O(N)
加入两个辅助栈实现O(1)时间复杂度获取栈中的最大值和最小值,典型的以空间换取时间。
代码实现:
// Java代码 class MyStack { public void push(int e) {// 新建MyStack数据结构的push函数 stack.push(e);// 元素入栈 // 判断是否需要更新minStack栈顶元素 if (minStack.isEmpty() || e < minStack.peek()) { minStack.push(e);// 入栈元素更小,更换栈顶元素 } else if (e >= minStack.peek()) { minStack.push(minStack.peek());// 不用更换栈顶元素 } // 判断是否需要更新maxStack栈顶元素 if (maxStack.isEmpty() || e > maxStack.peek()) { maxStack.push(e);// 入栈元素更大,更换栈顶元素 } else if (e <= maxStack.peek()) { maxStack.push(maxStack.peek());// 不用更换栈顶元素 } } public int pop() {// 新建MyStack数据结构的pop函数 // 三栈全部出栈 int ret = stack.pop(); minStack.pop(); maxStack.pop(); return ret; } public int getMin() {// O(1)时间返回最小值 return minStack.peek(); } public int getMax() {// O(1)时间返回最大值 return maxStack.peek(); } private Stack<Integer> stack = new Stack<>();// 存储栈 private Stack<Integer> minStack = new Stack<>();// 最小值辅助栈 private Stack<Integer> maxStack = new Stack<>();// 最大值辅助栈 }
// C++代码 class MyStack { public: void push(int e) {// 新建MyStack数据结构的push函数 stacks.push(e);// 元素入栈 // 判断是否需要更新minStack栈顶元素 if (minStack.empty() || e < minStack.top()) { minStack.push(e);// 入栈元素更小,更换栈顶元素 } else if (e >= minStack.top()) { minStack.push(minStack.top());// 不用更换栈顶元素 } // 判断是否需要更新maxStack栈顶元素 if (maxStack.empty() || e > maxStack.top()) { maxStack.push(e);// 入栈元素更大,更换栈顶元素 } else if (e <= maxStack.top()) { maxStack.push(maxStack.top());// 不用更换栈顶元素 } } void pop() {// 新建MyStack数据结构的pop函数 // 三栈全部出栈 stacks.pop(); minStack.pop(); maxStack.pop(); } int top() { return stacks.top(); } int getMin() {// O(1)时间返回最小值 return minStack.top(); } int getMax() {// O(1)时间返回最大值 return maxStack.top(); } private: stack<int> stacks;// 存储栈 stack<int> minStack;// 最小值辅助栈 stack<int> maxStack;// 最大值辅助栈 };
加载全部内容