Question:How would you design a stack which, in addition to push and pop, also has functions which return the minimum and maximum elements? Push, pop, min, max should all operate inO(1) time.
思路：1.用两个数组存最大值和最小值下标序列。保证max和min操作时间复杂度为0(1)。
2.每次push时，如果push值比当前最大值大，则更新最大值下标数组，该数组在该push值的下标位置处值为当前最大值（即指向前一个最大值），随后用push值更新最大值。否则将最大值下标数组在该push值的下标位置处赋值-1；同理更新最小值。
3.每次pop时，如果pop的值正好是当前最大值，则通过最大值下标数组找到当前最大值前一个最大值（即pop当前最大值后的最大值）。同理更新最小值。
public class MinMaxStack { public static int max= 5; public int stackItem[]; public int maxItem[]; public int minItem[]; public int top; public int maxIndex; public int minIndex; public MinMaxStack(){ stackItem = new int[max]; maxItem = new int[max]; minItem = new int[max]; top = -1; maxIndex = -1; minIndex = -1; } public static void main(String[] args) throws Exception{ MinMaxStack ss = new MinMaxStack(); // ss.print(); // for(int i=0;i<max;i++) // { // System.out.println("Push "+i+":"); // ss.push(i); // ss.print(); // } // ss.print(); // for(int i=0;i<max/2;i++) // { // System.out.println("Pop "+i+":"); // ss.pop(); // ss.print(); // } // ss.pop(); // ss.print(); ss.push(1); ss.push(2); ss.push(4); ss.push(3); ss.print(); } public void push(int data)throws Exception { top++; if(top >= max){ throw new Exception( "full");} else{ stackItem[top] = data; if(data>max()){ maxItem[top] = maxIndex; maxIndex = top; } else{ maxItem[top] = -1; } if(data < min()){ minItem[top] = minIndex; minIndex = top; } else{ minItem[top] = -1; } } } public int pop() throws Exception{ int res = -1; if(top <0){ throw new Exception( "empty"); } else{ res = stackItem[top]; if(top == maxIndex) maxIndex = maxItem[top]; if(top == minIndex) minIndex = minItem[top]; top--; } return res; } public int max(){ if(maxIndex >=0){ return stackItem[maxIndex]; } else { return Integer.MIN_VALUE; } } public int min(){ if(minIndex >=0){ return stackItem[minIndex]; } else { return Integer.MAX_VALUE; } } public void print() { System.out.print("The stack is:{"); for(int i=0;i<=top;i++) System.out.print(stackItem[i]+","); System.out.print("}" ); if(maxIndex > 0){ System.out.print(stackItem[maxIndex] ); } System.out.println(); System.out.println("The max item is:"+max()+"max index is:" + maxIndex); System.out.println("The min item is:"+min()+"min index is:" + minIndex); } }