-
题目:[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
-
思路:两个栈,一个正常存入,另一个栈存储第一个栈弹出的元素。因为第一个栈弹出的元素必定是栈顶元素,存入到另一个栈中就到了栈底,这样在第二个栈就相当于是队列,弹出的元素是我们第一个存入的元素。
-
代码:注意!不直接使用Stack,因为继承于Vector,加了锁效率低,而且Stack继承了Vector中无关的方法。
-
题目:
-
思路:同样是使用两个栈,一个是主栈,一个是最小栈。主栈正常存储元素,最小栈获取主栈的最小值。只不过这次,题目要求删除,增加操作的时间复杂度是O(1),那么就应该选择LinkedList实现类,因为链表增删改效率是O(1)。主栈进行正常的压入弹出,最小栈要注意:
- 初始化类的时候,往最小栈压入个int类型的最大值,方便后面操作。
- 往主栈压入元素时,最小栈要同时获取主栈中的最小值压入。这样的话,想一下栈顶元素是不是永远就是最小值了?那压入元素的时候怎么知道最小值呢?只要与当前栈顶元素比较就可以了,如果比栈顶元素小,那么压入的元素就是新的最小值,那么就把新元素压入栈顶;如果栈顶元素比压入的元素要小,那么栈顶元素依然是最小值,就继续压入栈顶的值。
- 弹出主栈栈顶元素时,要把最小栈的栈顶也弹出,因为最小栈与主栈栈顶元素是同时进来的,出去也要同时出去,才能保证最小值是最新的。
- 最后要获取最小值,就非常简单了,弹出最小栈的栈顶就可以了。
-
代码:注意!不直接使用Stack,因为继承于Vector,加了锁效率低,而且Stack继承了Vector中无关的方法。
package lapTop.Math; import java.util.Deque; import java.util.LinkedList; class MinStack { DequemainStack; //单独拎出来作为成员变量,所有方法共享。 Deque minStack; public MinStack() { mainStack = new LinkedList<>();//用LinkedList实现类,因为题目要求增删改效率要O(1) minStack = new LinkedList<>(); } public void push(int x) { //压入要同步,随时更新最小值 mainStack.push(x); //因为栈顶永远是最小值,只需要用新来的和最小栈栈顶比较即可。 minStack.push(Math.min(min(),x)); } public void pop() { mainStack.pop(); //要把最小栈的栈顶也弹出去,因为他们是同时进来的,同时出去才能更新最小值。 minStack.pop(); } public int top() { //如果这里用peek()的话可能会导致空指针异常。(IDEA的警告) return mainStack.element(); } public int min() { //如果这里用peek()的话可能会导致空指针异常。(IDEA的警告) return minStack.element(); } } -
感受:超,一点思路都没有,还得看官方题解。希望以后会更厉害。
Stack.element();
}
} -
感受:超,一点思路都没有,还得看官方题解。希望以后会更厉害。



