`

java实现一个栈，并提供取该栈中最大数的方法，复杂度O(1)

    博客分类：
  • JAVA
Java面试 
阅读更多

 

记得是哪个面试题里的，这里只想到一个简单的方法，大家看看对不对。。。

 

 

/**
 * @Project:      Test     
 * @File:         org.coffeesweet.test01.Test19.java
 * @Author:       coffeesweet
 * @Date:         2011-6-7
 * @Description:  2011 coffeesweet Inc. All rights reserved.
 */
package org.coffeesweet.test01;

import java.util.LinkedList;

/**
 * @author coffeesweet
 *
 */
public class Test19 {

	public static void main(String[] args){
		Long[] numList = new Long[]{1L,5L,3L,2L,1L,5L,7L,6L,7L,8L,-1L,-5L,2L,7L,2L,3L,5L,9L,9L};
		Test19 t19 = new Test19();
		MaxNumStack mns = t19.new MaxNumStack();
		for(int i=0;i<numList.length;i++){
			mns.push(numList[i]);
		}
		System.out.println(mns.pop());
		System.out.println(mns.pop());
		System.out.println(mns.top());
		System.out.println(mns.getMaxNum());
	}
	
	private class MaxNumStack{
		
		private LinkedList<Long> stackList = new LinkedList<Long>();
		private LinkedList<Long> maxNumList = new LinkedList<Long>();
		
		public void push(Long num){
			stackList.addLast(num);
			if(maxNumList.isEmpty()||(maxNumList.getLast().compareTo(num)<1)){
				maxNumList.addLast(num);
			}
		}
		
		public Long pop(){
			if(stackList.isEmpty())return null;
			if((maxNumList.getLast().compareTo(stackList.getLast())<1))maxNumList.removeLast();
			return stackList.removeLast();
		}
		
		public Long top(){
			return stackList.getLast();
		}
		
		public boolean isEmpty(){
			return stackList.isEmpty();
		}
		
		public Long getMaxNum(){
			if(maxNumList.isEmpty())return null;
			return maxNumList.getLast();
		}
	}
}
 
分享到：
| Listener Servlet和filter的应用
评论
19 楼 tengyue5i5j 2011-06-10  
Crusader 写道
竟然有这么多人投良好。。。
楼主的思路有问题，push的时候： 
if(maxNumList.isEmpty()||(maxNumList.getLast().compareTo(num)<1)){  
     maxNumList.addLast(num);  
}

导致多pop几次以后，就可能找不到最大数了
按你的思路，你的maxNumList必须存储所有的数字，并且排序。

如果数字的区间不是特别大的话，可以考虑除栈本身的数据结构外(不管是用顺序表还是链表)，用一个BitSet存储所有的数，在存储的时候相当于对所有数进行了排序，并且取最大值也很容易，然后每次pop的时候对相应位set 0就可以了


要改成小于等于1就行了，我试过了！
18 楼 coffeesweet 2011-06-09  
Crusader 写道
coffeesweet 写道

我的maxNumList并没有存储所有数字啊，比如我按顺序入栈这些数字：[1, 5, 3, 2, 1, 5, 7, 6, 7, 8, -1, -5, 2, 7, 2, 3, 5, 9, 9]，然后我的maxNumList存入的数字是：[1, 5, 5, 7, 7, 8, 9, 9]；

再然后我的栈连续POP两次以后变成：[1, 5, 3, 2, 1, 5, 7, 6, 7, 8, -1, -5, 2, 7, 2, 3, 5]，
这时我的maxNumList也变成了[1, 5, 5, 7, 7, 8]，

maxNumList.getLast()始终是目前栈的最大数啊。难道是我的main里的测试数据有问题？？？有没想到的情况？？？


不好意思，是我想错了。。。


没关系，只不过是被投个新手帖，然后做12道题，扣10分而已，习惯了。再说这个东西就是面试题瞎做做。逻辑没错，不误导新人就行。
17 楼 shbgreenery 2011-06-09  
这个东西只是看看吧。
16 楼 Crusader 2011-06-09  
coffeesweet 写道

我的maxNumList并没有存储所有数字啊，比如我按顺序入栈这些数字：[1, 5, 3, 2, 1, 5, 7, 6, 7, 8, -1, -5, 2, 7, 2, 3, 5, 9, 9]，然后我的maxNumList存入的数字是：[1, 5, 5, 7, 7, 8, 9, 9]；

再然后我的栈连续POP两次以后变成：[1, 5, 3, 2, 1, 5, 7, 6, 7, 8, -1, -5, 2, 7, 2, 3, 5]，
这时我的maxNumList也变成了[1, 5, 5, 7, 7, 8]，

maxNumList.getLast()始终是目前栈的最大数啊。难道是我的main里的测试数据有问题？？？有没想到的情况？？？


不好意思，是我想错了。。。
15 楼 coffeesweet 2011-06-09  
抛出异常的爱 写道
Crusader 写道
竟然有这么多人投良好。。。
楼主的思路有问题，push的时候： 
if(maxNumList.isEmpty()||(maxNumList.getLast().compareTo(num)<1)){  
     maxNumList.addLast(num);  
}

导致多pop几次以后，就可能找不到最大数了
按你的思路，你的maxNumList必须存储所有的数字，并且排序。

如果数字的区间不是特别大的话，可以考虑除栈本身的数据结构外(不管是用顺序表还是链表)，用一个BitSet存储所有的数，在存储的时候相当于对所有数进行了排序，并且取最大值也很容易，然后每次pop的时候对相应位set 0就可以了

同上

送一程



我的maxNumList并没有存储所有数字啊，比如我按顺序入栈这些数字：[1, 5, 3, 2, 1, 5, 7, 6, 7, 8, -1, -5, 2, 7, 2, 3, 5, 9, 9]，然后我的maxNumList存入的数字是：[1, 5, 5, 7, 7, 8, 9, 9]；

再然后我的栈连续POP两次以后变成：[1, 5, 3, 2, 1, 5, 7, 6, 7, 8, -1, -5, 2, 7, 2, 3, 5]，
这时我的maxNumList也变成了[1, 5, 5, 7, 7, 8]，

maxNumList.getLast()始终是目前栈的最大数啊。难道是我的main里的测试数据有问题？？？有没想到的情况？？？
14 楼 coffeesweet 2011-06-09  
抛出异常的爱 写道
Crusader 写道
竟然有这么多人投良好。。。
楼主的思路有问题，push的时候： 
if(maxNumList.isEmpty()||(maxNumList.getLast().compareTo(num)<1)){  
     maxNumList.addLast(num);  
}

导致多pop几次以后，就可能找不到最大数了
按你的思路，你的maxNumList必须存储所有的数字，并且排序。

如果数字的区间不是特别大的话，可以考虑除栈本身的数据结构外(不管是用顺序表还是链表)，用一个BitSet存储所有的数，在存储的时候相当于对所有数进行了排序，并且取最大值也很容易，然后每次pop的时候对相应位set 0就可以了

同上

送一程



呵呵，一直在内网，没有切出来，老早前的一个面试题，有同学问我就放出来了，没怎么再看。当时就这么随便写的，不考虑线程问题，逻辑应该没问题吧？？
嘿嘿，不管怎么样，谢谢大家的关注，我再看看。
13 楼 抛出异常的爱 2011-06-09  
Crusader 写道
竟然有这么多人投良好。。。
楼主的思路有问题，push的时候： 
if(maxNumList.isEmpty()||(maxNumList.getLast().compareTo(num)<1)){  
     maxNumList.addLast(num);  
}

导致多pop几次以后，就可能找不到最大数了
按你的思路，你的maxNumList必须存储所有的数字，并且排序。

如果数字的区间不是特别大的话，可以考虑除栈本身的数据结构外(不管是用顺序表还是链表)，用一个BitSet存储所有的数，在存储的时候相当于对所有数进行了排序，并且取最大值也很容易，然后每次pop的时候对相应位set 0就可以了

同上

送一程
12 楼 Crusader 2011-06-09  
竟然有这么多人投良好。。。
楼主的思路有问题，push的时候： 
if(maxNumList.isEmpty()||(maxNumList.getLast().compareTo(num)<1)){  
     maxNumList.addLast(num);  
}

导致多pop几次以后，就可能找不到最大数了
按你的思路，你的maxNumList必须存储所有的数字，并且排序。

如果数字的区间不是特别大的话，可以考虑除栈本身的数据结构外(不管是用顺序表还是链表)，用一个BitSet存储所有的数，在存储的时候相当于对所有数进行了排序，并且取最大值也很容易，然后每次pop的时候对相应位set 0就可以了
11 楼 tengyue5i5j 2011-06-09  
push(Long num){  
if(maxNumList.isEmpty()||(maxNumList.getLast().compareTo(num)<1)){  
是不是要改成小于等于1啊  还有pop的时候也是的？？？？？
10 楼 agapple 2011-06-09  
kimmking 写道
好吧，我点错了投票

linkedlist实现stack

本末倒置。


人家偷懒而已，不想自己实现一个链表。

前段时间也用Deque实现Stack + Queue一起结合的功能
9 楼 kimmking 2011-06-09  
好吧，我点错了投票

linkedlist实现stack

本末倒置。
8 楼 kingkan 2011-06-09  
栈的push跟pop是要加锁的。。。
7 楼 java_user 2011-06-09  
和我想的一致
6 楼 freish 2011-06-09  
Nanigac 写道
如果非要这么做，多维护一个list还不如只保持最后一个最大值，呵呵～


这个方法很好啊
5 楼 lwjlaser 2011-06-09  
构建栈为什么不用数组？
4 楼 jewelknife 2011-06-07  
楼主要求时间复杂度为O（1）,按照楼主的思路，维护两个list，一个做stack，另一个维护一个大小顺序，这样每次插入的时候需要对存大小顺序的list做修改。（用插入排序，时间复杂度O(log2n)小于n）.这样可以满足取该栈中最大数的方法复杂度为O（1）.缺点：消耗2倍内存。

再者就是用一个变量记最大值，缺点，不管出栈入栈都要维护这个变量。入栈比较一下就行，出栈如果是最大值，则需要遍历数组找出新的最大值附给变量。优点：插入比上面快，内存暂用小。缺点：出栈可能需要排序。
3 楼 Nanigac 2011-06-07  
如果非要这么做，多维护一个list还不如只保持最后一个最大值，呵呵～
2 楼 Nanigac 2011-06-07  
构建栈的时候用了2个List

求最大值应该很简单的吧，遍历一次就可以啊。
1 楼 抛出异常的爱 2011-06-07  
楼主你写的应该不好用。。。。
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics