This optimization is also called "Convex Hull Trick" because it is either maintaining an upper convex hull ( decreasing slopes ) or a lower convex hull. Also note that there are problems that do not necessarily have to be monotonous but st…

A deque ( double ended queue ) is a data structure that supports push/ pop from both ends with constant time complexity. It can be used to optimize algorithms that deal with monotonous properties. The first time I saw this data structure, …

Stacks can be used to maintain for monotonous properties, can optimize for many problems, but only if you can discover the monotony in the problem. Here are some problems for exercise from the ant book. 3250 -- Bad Hair Day POJ 3250 Bad Ha…