定义栈的数据结构, 请在该类型中实现一个能够得到栈中所含最小元素的 min 函数 (时间复杂度应为 O(1)).
由于本身给了 import java.util.Stack; 所以感觉可以使用 JDK 自带的栈
思路: 用两个栈进行记录, s1 记录全部, s2 记录各个时刻最小值
源码如下:
- import java.util.Stack;
- public class Solution {
- Stack<Integer> s1 = new Stack();
- Stack<Integer> s2 = new Stack();
- public void push(int node) {
- s1.push(node);
- if(s2.empty())
- s2.push(node);
- else{
- if(node<s2.peek())
- s2.push(node);
- }
- }
- public void pop() {
- if(s1.peek()==s2.peek()){
- s1.pop();
- s2.pop();
- }else{
- s1.pop();
- }
- }
- public int top() {
- return s1.peek();
- }
- public int min() {
- return s2.peek();
- }
- }
来源: http://www.bubuko.com/infodetail-3376847.html