题目 定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中,调用min、push及pop的时间复杂度都是O(1)。
分析 新建一个数据栈,一个辅助栈。
入栈:
数据栈就是正常压入即可。
【【剑指offer】包含min函数的栈】而对于辅助栈,如果每次都能把最小元素压入辅助栈,那么就能保证辅助栈的栈顶一直是最小元素。所以压入的时候,把每次最小的元素(之前的最小元素与新入栈元素的值进行比较),保存起来放到辅助栈中。
出栈:当最小元素从数据栈内被弹出之后,同时弹出辅助栈的栈顶元素,此时辅助栈的新栈顶元素就是下一个最小值。
代码
package com.Queue;
import java.util.Stack;
//定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。
//在该栈中,调用min、push及pop的时间复杂度都是O(1)。
public class StackWithMin {
Stack stack_data = https://www.it610.com/article/new Stack();
Stack stack_min = new Stack();
public void push(int node){
stack_data.push(node);
if(stack_min.empty() || stack_min.peek() > node){
stack_min.push(node);
}else {
stack_min.push(stack_min.peek());
}
}public void pop(){
if(!stack_data.empty()){
stack_data.pop();
stack_min.pop();
}
}public int min(){
return stack_min.pop();
}}
推荐阅读
- 牛牛以前在老师那里得到了一个正整数数对(x, y), 牛牛忘记他们具体是多少了。 但是牛牛记得老师告诉过他x和y均不大于n, 并且x除以y的余数大于等于k。 牛
- 剑指offer|剑指offer、牛客-二维数组的查找
- 剑指offer|牛客网_剑指Offer_Python实现_更新中
- 剑指offer|牛客网剑指offer——python实现(更新15题)
- 剑指Offer__17、树的子结构
- 剑指Offer__19、顺时针打印矩阵
- 剑指Offer__18、二叉树的镜像
- 输入一个英文句子,将每个单词的第一个字母改成大写字母。
- Leetcode|【leetcode】 91. 解码方法 & 【剑指Offer】 46.把数字翻译成字符串