Groups
Category
The exchange argument proves a greedy algorithm is optimal by swapping out-of-order choices in any supposed optimal solution until it matches the greedy one without making it worse.
A monotonic deque is a double-ended queue that keeps elements in increasing or decreasing order so that the front always holds the current optimum (min or max).