首页 > 学院 > 开发设计 > 正文

定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。时间复杂度都是O(1)

2019-11-08 02:23:02
字体:
来源:转载
供稿:网友

定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。要求:使得时间复杂度都是O(1)

完成如下的函数:

import java.util.Stack;public class Solution {        public void push(int node) {            }        public void pop() {            }        public int top() {            }        public int min() {            }}

思路:用空间换时间,用一个辅助栈记录当前栈中的最小值。辅助栈元素个数和数据栈保持一样的数目。例如一次压入数据栈数字序列为:

3,2,4,1,5  那么一次压入辅助栈的为:3,2,2,1,1

当每次压入数据栈的元素小余辅助站的元素的时候,才把新元素压入辅助栈,否则把辅助站栈顶元素去到压入辅助栈,保持两个栈元素个数一致。

备注:Stack.Peek 与 stack.pop 的区别

相同点:大家都返回栈顶的值。

不同点:peek 不改变栈的值(不删除栈顶的值),pop会把栈顶的值删除。

package com.mytest.mymain;import java.util.Stack;public class MinStack {    PRivate Stack<Integer> data_stack=new Stack<Integer>();    private Stack<Integer> min_stack=new Stack<Integer>();        public void push(int node) {//进栈        if(min_stack.isEmpty() ||min_stack.peek()>=node){        	min_stack.push(node);        }else{        	min_stack.push(min_stack.peek());        }        data_stack.push(node);    }        public void pop() {//出栈    	if(data_stack.empty() || min_stack.empty())    		return;    	    	data_stack.pop();    	min_stack.pop();    }        public int top() {//取得栈顶元素    	if(!data_stack.empty()){	          return data_stack.peek();    	}    	return 0;    }        public int min() {//取得最小值    	if(!min_stack.empty()){    		        return min_stack.peek();    }    	return 0;    }}
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表