The solution to this problem says we cannot just have another stack for max values because of duplicates. But in my code I did use the stack of max values, and it just has duplicates (I push into it if item being pushed to the owner stack is >= the top element in my stack of max values. If I pop and the value is equal to top of max, I pop it from both stacks). Is there a bug somewhere? I tested with {1, 2, 2, 1, 3, 4, 5, 5, 1, 2, 3} by popping and checking and the test passed… But I don’t know if I missed something. My solution seem to me more clean than storing pairs. Also a stack of pairs essentially seems to store the same information as the stack of duplicates. The only case where it is better is when there are a lot of duplicates (which is often the case) and a stack of pairs saves space.
9.1. Stack with max
Hey Mariia,
I just checked our book but don’t see the statement about we cannot have another stack for max values because of duplicates. Basically I think your algorithm is identical to what we had, and I agree with that using a pair is similar to having another stack storing the max values. Please let me know if you have any other question.
I just had the exact same question.
In the Java version of the book, this is problem 8.1.
The solution says (page 109): “We cannot store the sequence of maximum values in a separate stack because of the possibility of duplicates”.
Is it a bug in the book?
Hi @rem,
This is not a bug since if you store a sequence of that, it makes no difference with the previous algorithm while we are aiming to improve space complexity here.