论坛首页 → 综合技术论坛 →

百度一面算法题(常数时间内求栈中最大值)

浏览 24998 次
锁定老帖子 主题：百度一面算法题(常数时间内求栈中最大值)
精华帖 (0) :: 良好帖 (3) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
  • yeshaoting
  • 等级: 初级会员
  • 性别:
  • 文章: 136
  • 积分: 90
  • 来自: 北京
   发表时间：2011-10-24   最后修改：2011-10-24

 


算法描述：

一个栈stack，具有push和pop操作，其时间复杂度皆为O(1)。

设计算法max操作，求栈中的最大值，该操作的时间复杂度也要求为O(1)。

可以修改栈的存储方式，push，pop的操作，但是要保证O(1)的时间复杂度，空间时间复杂度无要求。


思路：

我借助一个变量count和一个数组空间（其实就是一个栈）完成该时间复杂度为O(1)的算法设计。

 
返回顶楼
         
  • YuHuang.Neil
  • 等级: 初级会员
  • 性别:
  • 文章: 8
  • 积分: 30
  • 来自: 北京
   发表时间：2011-11-03  
我的实现是



import java.util.ArrayList;
import java.util.EmptyStackException;
import java.lang.NullPointerException;

public class StackForPriorImpl<E extends Comparable<E>> implements
IStackForPrior<E> {

private int numberOfObject;
private ArrayList<E> dataForOrginal;
private ArrayList<E> dataForMaximun;
private ArrayList<E> dataForMinimun;
private E maxElement;
private E minElement;

public StackForPriorImpl(){
this.numberOfObject = 0;
this.dataForOrginal = new ArrayList<E>();
this.dataForMaximun = new ArrayList<E>();
this.dataForMinimun = new ArrayList<E>();
}

@Override
public void push(E e) {

if(e==null){
throw new NullPointerException();
}

dataForOrginal.add(e);

if(numberOfObject==0){
maxElement = e;
minElement = e;
this.dataForMaximun.add(maxElement);
this.dataForMinimun.add(minElement);
}else{

if(e.compareTo(maxElement)>0){
dataForMaximun.add(e);
maxElement = e;
}else{
dataForMaximun.add(maxElement);
}

if(e.compareTo(minElement)<0){
dataForMinimun.add(e);
minElement = e;
}else{
dataForMinimun.add(minElement);
}
}

++numberOfObject;

}

@Override
public E pop() {

if(numberOfObject==0) {
throw new EmptyStackException();
}

int index = --numberOfObject;

dataForMaximun.remove(index);
maxElement = dataForMaximun.get(index-1);

dataForMinimun.remove(index);
minElement = dataForMinimun.get(index-1);

E e = dataForOrginal.get(index);
dataForOrginal.remove(index);
return e;
}

@Override
public E peekMedian() {

if(numberOfObject==0){
throw new EmptyStackException();
}

Object[] elementArray=this.dataForOrginal.toArray();
int lengthOfElementArray = elementArray.length;
quickSort(elementArray,0,lengthOfElementArray-1);

return (E)elementArray[lengthOfElementArray/2];
}

@Override
public E peekMaximum() {

if(numberOfObject==0){
throw new EmptyStackException();
}

int index = numberOfObject - 1;
return this.dataForMaximun.get(index);
}

@Override
public E peekMinimum() {

if(numberOfObject==0) {
throw new EmptyStackException();
}

int index = numberOfObject - 1;
return this.dataForMinimun.get(index);
}

@Override
public int size() {

return this.numberOfObject;
}

private static <E> void quickSort(E[] elementArray,int low,int high){
if(low<high){
int q = partition(elementArray,low,high);
quickSort(elementArray,low,q-1);
quickSort(elementArray,q+1,high);
}
}

private static <E> int partition(E[] elementArray,int low,int high){
int i = low, j=high+1;
E e= elementArray[low];
while(true){
while(elementArray[++i].toString().compareTo(e.toString())<0 && i<high);
while(elementArray[--j].toString().compareTo(e.toString())>0);
if(i>=j) break;

E temp = elementArray[i];
elementArray[i]=elementArray[j];
elementArray[j]=temp;
}

elementArray[low] = elementArray[j];
elementArray[j]=e;

return j;
}

public static void main(String[] args){
StackForPriorImpl<Integer> stack=new StackForPriorImpl<Integer>();

stack.push(new Integer(2));
stack.push(new Integer(1));
stack.push(new Integer(2));
stack.push(new Integer(2));
stack.push(new Integer(6));
stack.push(new Integer(4));
stack.push(new Integer(2));
stack.push(new Integer(5));

System.out.println("size = "+stack.size());
System.out.println("peekMaximun = "+stack.peekMaximum().toString());
System.out.println("peekMinimun = "+stack.peekMinimum().toString());
System.out.println("peekMedian = "+stack.peekMedian().toString());

}
}
返回顶楼
          回帖地址
0 请登录后投票
  • yeshaoting
  • 等级: 初级会员
  • 性别:
  • 文章: 136
  • 积分: 90
  • 来自: 北京
   发表时间：2011-11-04  
YuHuang.Neil 写道
我的实现是



import java.util.ArrayList;
import java.util.EmptyStackException;
import java.lang.NullPointerException;

public class StackForPriorImpl<E extends Comparable<E>> implements
IStackForPrior<E> {

private int numberOfObject;
private ArrayList<E> dataForOrginal;
private ArrayList<E> dataForMaximun;
private ArrayList<E> dataForMinimun;
private E maxElement;
private E minElement;

public StackForPriorImpl(){
this.numberOfObject = 0;
this.dataForOrginal = new ArrayList<E>();
this.dataForMaximun = new ArrayList<E>();
this.dataForMinimun = new ArrayList<E>();
}

@Override
public void push(E e) {

if(e==null){
throw new NullPointerException();
}

dataForOrginal.add(e);

if(numberOfObject==0){
maxElement = e;
minElement = e;
this.dataForMaximun.add(maxElement);
this.dataForMinimun.add(minElement);
}else{

if(e.compareTo(maxElement)>0){
dataForMaximun.add(e);
maxElement = e;
}else{
dataForMaximun.add(maxElement);
}

if(e.compareTo(minElement)<0){
dataForMinimun.add(e);
minElement = e;
}else{
dataForMinimun.add(minElement);
}
}

++numberOfObject;

}

@Override
public E pop() {

if(numberOfObject==0) {
throw new EmptyStackException();
}

int index = --numberOfObject;

dataForMaximun.remove(index);
maxElement = dataForMaximun.get(index-1);

dataForMinimun.remove(index);
minElement = dataForMinimun.get(index-1);

E e = dataForOrginal.get(index);
dataForOrginal.remove(index);
return e;
}

@Override
public E peekMedian() {

if(numberOfObject==0){
throw new EmptyStackException();
}

Object[] elementArray=this.dataForOrginal.toArray();
int lengthOfElementArray = elementArray.length;
quickSort(elementArray,0,lengthOfElementArray-1);

return (E)elementArray[lengthOfElementArray/2];
}

@Override
public E peekMaximum() {

if(numberOfObject==0){
throw new EmptyStackException();
}

int index = numberOfObject - 1;
return this.dataForMaximun.get(index);
}

@Override
public E peekMinimum() {

if(numberOfObject==0) {
throw new EmptyStackException();
}

int index = numberOfObject - 1;
return this.dataForMinimun.get(index);
}

@Override
public int size() {

return this.numberOfObject;
}

private static <E> void quickSort(E[] elementArray,int low,int high){
if(low<high){
int q = partition(elementArray,low,high);
quickSort(elementArray,low,q-1);
quickSort(elementArray,q+1,high);
}
}

private static <E> int partition(E[] elementArray,int low,int high){
int i = low, j=high+1;
E e= elementArray[low];
while(true){
while(elementArray[++i].toString().compareTo(e.toString())<0 && i<high);
while(elementArray[--j].toString().compareTo(e.toString())>0);
if(i>=j) break;

E temp = elementArray[i];
elementArray[i]=elementArray[j];
elementArray[j]=temp;
}

elementArray[low] = elementArray[j];
elementArray[j]=e;

return j;
}

public static void main(String[] args){
StackForPriorImpl<Integer> stack=new StackForPriorImpl<Integer>();

stack.push(new Integer(2));
stack.push(new Integer(1));
stack.push(new Integer(2));
stack.push(new Integer(2));
stack.push(new Integer(6));
stack.push(new Integer(4));
stack.push(new Integer(2));
stack.push(new Integer(5));

System.out.println("size = "+stack.size());
System.out.println("peekMaximun = "+stack.peekMaximum().toString());
System.out.println("peekMinimun = "+stack.peekMinimum().toString());
System.out.println("peekMedian = "+stack.peekMedian().toString());

}
}

写得很好~~
跟我当时的做法是一样的.
返回顶楼
          回帖地址
0 请登录后投票
  • yeshaoting
  • 等级: 初级会员
  • 性别:
  • 文章: 136
  • 积分: 90
  • 来自: 北京
   发表时间：2011-11-04  
YuHuang.Neil 写道
我的实现是



import java.util.ArrayList;
import java.util.EmptyStackException;
import java.lang.NullPointerException;

public class StackForPriorImpl<E extends Comparable<E>> implements
IStackForPrior<E> {

private int numberOfObject;
private ArrayList<E> dataForOrginal;
private ArrayList<E> dataForMaximun;
private ArrayList<E> dataForMinimun;
private E maxElement;
private E minElement;

public StackForPriorImpl(){
this.numberOfObject = 0;
this.dataForOrginal = new ArrayList<E>();
this.dataForMaximun = new ArrayList<E>();
this.dataForMinimun = new ArrayList<E>();
}

@Override
public void push(E e) {

if(e==null){
throw new NullPointerException();
}

dataForOrginal.add(e);

if(numberOfObject==0){
maxElement = e;
minElement = e;
this.dataForMaximun.add(maxElement);
this.dataForMinimun.add(minElement);
}else{

if(e.compareTo(maxElement)>0){
dataForMaximun.add(e);
maxElement = e;
}else{
dataForMaximun.add(maxElement);
}

if(e.compareTo(minElement)<0){
dataForMinimun.add(e);
minElement = e;
}else{
dataForMinimun.add(minElement);
}
}

++numberOfObject;

}

@Override
public E pop() {

if(numberOfObject==0) {
throw new EmptyStackException();
}

int index = --numberOfObject;

dataForMaximun.remove(index);
maxElement = dataForMaximun.get(index-1);

dataForMinimun.remove(index);
minElement = dataForMinimun.get(index-1);

E e = dataForOrginal.get(index);
dataForOrginal.remove(index);
return e;
}

@Override
public E peekMedian() {

if(numberOfObject==0){
throw new EmptyStackException();
}

Object[] elementArray=this.dataForOrginal.toArray();
int lengthOfElementArray = elementArray.length;
quickSort(elementArray,0,lengthOfElementArray-1);

return (E)elementArray[lengthOfElementArray/2];
}

@Override
public E peekMaximum() {

if(numberOfObject==0){
throw new EmptyStackException();
}

int index = numberOfObject - 1;
return this.dataForMaximun.get(index);
}

@Override
public E peekMinimum() {

if(numberOfObject==0) {
throw new EmptyStackException();
}

int index = numberOfObject - 1;
return this.dataForMinimun.get(index);
}

@Override
public int size() {

return this.numberOfObject;
}

private static <E> void quickSort(E[] elementArray,int low,int high){
if(low<high){
int q = partition(elementArray,low,high);
quickSort(elementArray,low,q-1);
quickSort(elementArray,q+1,high);
}
}

private static <E> int partition(E[] elementArray,int low,int high){
int i = low, j=high+1;
E e= elementArray[low];
while(true){
while(elementArray[++i].toString().compareTo(e.toString())<0 && i<high);
while(elementArray[--j].toString().compareTo(e.toString())>0);
if(i>=j) break;

E temp = elementArray[i];
elementArray[i]=elementArray[j];
elementArray[j]=temp;
}

elementArray[low] = elementArray[j];
elementArray[j]=e;

return j;
}

public static void main(String[] args){
StackForPriorImpl<Integer> stack=new StackForPriorImpl<Integer>();

stack.push(new Integer(2));
stack.push(new Integer(1));
stack.push(new Integer(2));
stack.push(new Integer(2));
stack.push(new Integer(6));
stack.push(new Integer(4));
stack.push(new Integer(2));
stack.push(new Integer(5));

System.out.println("size = "+stack.size());
System.out.println("peekMaximun = "+stack.peekMaximum().toString());
System.out.println("peekMinimun = "+stack.peekMinimum().toString());
System.out.println("peekMedian = "+stack.peekMedian().toString());

}
}


扩展求中间值用到了快速排序.
我看到这个起先还以为你想错了呢.嘿嘿

另外,IStackForPrior<E>应该是你自己定义的接口吧!
想必这是就平时用到的程序...
返回顶楼
          回帖地址
0 请登录后投票
  • vieri122
  • 等级: 初级会员
  • 性别:
  • 文章: 324
  • 积分: 0
  • 来自: 北京
   发表时间：2011-11-04  
没太看懂题目的意思。简单说一下我的思路
挨个pop，用一个变量保存最大值即可？
返回顶楼
          回帖地址
0 请登录后投票
  • tswwz
  • 等级: 初级会员
  • 性别:
  • 文章: 7
  • 积分: 30
  • 来自: 上海
   发表时间：2011-11-04  
ls貌似没理解题目意思啊

按照题目的要求，其实是想直接就取出stack中最大值，提示说可以修改pop和push算法。

其实就是告诉你可以通过修改pop和push的实现记录下当前stack中的最大值。



考虑到stack中数据有可能重复，实际上要找个O（1）复杂度的算法还是有点难。

返回顶楼
          回帖地址
0 请登录后投票
  • tswwz
  • 等级: 初级会员
  • 性别:
  • 文章: 7
  • 积分: 30
  • 来自: 上海
   发表时间：2011-11-04  
可以考虑与当前stack维护对应的代表stack对应位置的最大值的栈MaxStack

对于栈stack

push元素 valueA时
           maxValue = popMaxStack();  pushMaxStack(maxValue);

           if  (valueA >= maxValue)   pushStack(valueA) ; pushMaxStack(valueA);
           if  (valueA < maxValue)    pushStack(valueA) ; pushMaxStack(maxValue);

pop元素
           maxValue = popMaxStack();  pushMaxStack(maxValue);
           valueA = popStack();
           popMaxStack();


这样取最大值时，直接  maxValue = popMaxStack();pushMaxStack(maxValue);就ok了。
返回顶楼
          回帖地址
0 请登录后投票
  • yeshaoting
  • 等级: 初级会员
  • 性别:
  • 文章: 136
  • 积分: 90
  • 来自: 北京
   发表时间：2011-11-04  
vieri122 写道
没太看懂题目的意思。简单说一下我的思路
挨个pop，用一个变量保存最大值即可？

挨个pop,总的时间复杂度就是O(n)了.
返回顶楼
          回帖地址
0 请登录后投票
  • yeshaoting
  • 等级: 初级会员
  • 性别:
  • 文章: 136
  • 积分: 90
  • 来自: 北京
   发表时间：2011-11-04  
vieri122 写道
没太看懂题目的意思。简单说一下我的思路
挨个pop，用一个变量保存最大值即可？

挨个pop,总的时间复杂度就是O(n)了.
这道题就是考的怎么用空间换时间.
返回顶楼
          回帖地址
0 请登录后投票
  • yeshaoting
  • 等级: 初级会员
  • 性别:
  • 文章: 136
  • 积分: 90
  • 来自: 北京
   发表时间：2011-11-04  
tswwz 写道
可以考虑与当前stack维护对应的代表stack对应位置的最大值的栈MaxStack

对于栈stack

push元素 valueA时
           maxValue = popMaxStack();  pushMaxStack(maxValue);

           if  (valueA >= maxValue)   pushStack(valueA) ; pushMaxStack(valueA);
           if  (valueA < maxValue)    pushStack(valueA) ; pushMaxStack(maxValue);

pop元素
           maxValue = popMaxStack();  pushMaxStack(maxValue);
           valueA = popStack();
           popMaxStack();


这样取最大值时，直接  maxValue = popMaxStack();pushMaxStack(maxValue);就ok了。

确实是有额外用到一个栈空间.
我的push元素想法跟你一样.
但是没太看懂你的pop元素.
返回顶楼
          回帖地址
0 请登录后投票
论坛首页 → 综合技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics