Store indices, not values. Values can be looked up; indices are needed for expiry checking. Pop from back: while deque not empty AND arr[back] (<=/>= depending on min/max) arr[i], pop. Pop from front: while front index is out of window, pop. Query: deque.front() gives the index of the optimal element in the current window. Test the template on the sliding window maximum problem first. Once it works, adapt for specific DP transitions.
Time complexity: .
Space complexity: in time and in space.