Stack<Integer> st= new Stack<Integer>();
int max=(int) st.peek();
int top=0;
for(Integer loopVal:st)
{
if(max<loopVal)
max=loopVal;
}
System.out.println(max);
This code, which finds the maximum value in a stack, is working perfectly fine, but I wish to optimize its performance so that it can handle a very large stack. Can someone suggest a better algorithm?
The complexity of your algorithm O(n) - linear. You will need to process all elements before finding maximum. With given data structure you won't be get better complexity.
The only one option is to have Sorted data structure, where elements are ordered. This allow you to get maximum with O(1) complexity, but sorting itself takes O(n*log(n)) which is makes no sense if you need to get max element only.
There isn't a way to get the max from the stack in a non linear time. In fact, elements in the stack don't have to be comparable, and hence the idea of max doesn't exist for every T you can put in the Stack.
You can roll your own implementation which works for Comparable<T> or just integers where you maintain two stacks, one for elements and the other of max elements, the max stack will maintain the current max, and when you pop, you pop from both stacks.
O(n) is the best time complexity you can get while searching for the max element in the stack as the maximum element can be anywhere on the stack. One thing you can do is while making the stack, that is while inserting the elements into the stack compare the values with a max variable and update the max variable if the value being inserted is greater than the max variable value. Insertion will also take linear time but it is still better than finding the max element separately after the stack is made. The problem with this method is if you pop elements from the stack, you might pop the max element sometime and there is know way to find the new max value without scanning the stack.
Depending on your actual requirement you can make another trade off.
At the storage cost of 1 Integer object, you can get your max value with complexity O(1) without sorting, with O(1) cost for PUSH and with O(n) cost when popping elements from stack.
public class IntStackWithMax {
private Integer maxVal = Integer.MIN_VALUE;
private Vector<Integer> values = new Vector<Integer>();
// cost O(1)
public Integer getMaxVal() {
return maxVal;
}
//cost O(1)
public boolean push(Integer item) {
maxVal = Math.max(maxVal, item);
return values.add(item);
}
//cost O(n) (!!!)
public Integer pop() {
Integer result = values.remove(values.size() - 1);
maxVal = Collections.max(values);
return result;
}
//cost O(1)
public Integer peek() {
return values.lastElement();
}
}
Please also note that this is NOT thread safe.
If space complexity can be compromised, you can create another stack and keep pushing minimum value when ever you push a new minimum into the original stack ...
