本文共 2578 字,大约阅读时间需要 8 分钟。
【题目】
实现一个特殊的栈, 在实现栈的基本功能的基础上, 在实现返回栈中最小元素的操作。
【要求】
1. pop, push, getMIn操作的时间复杂度都是O(1)。
2. 设计的栈类型可以使用现成的栈结构。
【难度】
一星
【方案1】
返回栈中最小元素, 我们可以遍历整个栈, 但是要求getMin的时间复杂度为O(1), 我们只好另想办法。
我们可以牺牲空间来换取时间, 设计两个栈——stackData, stackMin
stackData用来正常存取数据, stackMin用来记录stackData中的最小数字。
压入数据规则:
1. 往stackData中压入一个新数字newNum
2. 如果stackMin为空, 往stackMin中压入newNum
3. 如果stackMin不为空, 比较stackMin的栈顶元素和newNum, 如果newNum小于栈顶元素, 把newNum压入stackMin, 否则不进行操作
退栈操作:
1. stackMin栈顶存的是目前为止, stackData中的最小数字, 所以stackMin的栈顶数字只可能小于等于stackData中的数字。
2. stackData弹出栈顶元素, 如果这个元素等于stackMin的栈顶元素, stackMin弹出栈顶元素
3..如果这个元素大于stackMin的栈顶元素, 不进行操作。
getMin:
stackMin的栈顶元素就是目前为止stackData栈的最小元素。
【代码实现】
package 栈和队列;import java.util.Stack;class MyStack1{ private StackstackData; private Stack stackMin; public MyStack1(){ this.stackData = new Stack (); this.stackMin = new Stack (); } public void push(int newNum){ this.stackData.push(newNum); if(this.stackMin.isEmpty()){ this.stackMin.push(newNum); }else if(this.getMin() >= newNum){ this.stackMin.push(newNum); } } public int pop(){ if(this.stackData.isEmpty()){ throw new RuntimeException("Your stack is Empty"); } int value = this.stackData.pop(); if(value == this.getMin()){ this.stackMin.pop(); } } public int getMin(){ if(this.stackMin.isEmpty()){ throw new RuntimeException("Your stack is empty."); } return this.stackMin.peek(); }}
【方案2】
入栈规则:
其它的都和方案1相同, 但是当newNum大于stackMin的栈顶元素时, 把stackMin的栈顶元素重复压栈
弹出规则:
1.如果stackData为空, 抛出错误
2.否则把stackData的栈顶元素弹出, stackMin的栈顶元素也弹出
【实现代码】
package 栈和队列;import java.util.Stack;public class MyStack2 { private Stack方案一入栈的时候比方案2节省一点空间, 方案二比方案1出栈的时候节省一点时间。stackData; private Stack stackMin; public MyStack2() { this.stackData = new Stack (); this.stackMin = new Stack (); } public void push(int newNum) { this.stackData.push(newNum); if(this.stackMin.isEmpty()) { this.stackMin.push(newNum); }else if(newNum <= this.getMin()) { this.stackMin.push(newNum); }else { this.stackMin.push(this.getMin()); } } public int pop(){ if(this.stackData.isEmpty()) { throw new RuntimeException("Your stack is empty."); } int value = this.stackData.pop(); this.stackMin.pop(); return value; } public int getMin() { if(this.stackMin.isEmpty()) { throw new RuntimeException("Your stack is empty."); } return this.stackMin.peek(); }}
转载地址:http://bhaii.baihongyu.com/