PelatihThe two-pointer technique walks two indices through one or two sorted sequences, advancing whichever the condition dictates, so that each element is visited once. A monotonic deque is a double-ended queue of indices whose values are kept in decreasing (or increasing) order, so that the maximum (or minimum) of a sliding window is at its front at every step. A sweep line solves interval problems by sorting the intervals’ endpoints as events and processing them in order while maintaining a running state.
Contoh
Example 21.3 (A window with at most two venues)
“A parent order’s fills are listed in time order with the venue of each. Find the longest run of consecutive fills that touches at most two venues.” Clarify: runs are contiguous; venues are labels. Brute force checks every window, with a set per start. Improve with the two-pointer technique (Definition 21.1): extend the right end one fill at a time, keep a count per venue in the window, and while more than two venues have a positive count, advance the left end and decrement. Each fill enters and leaves the window once: time, extra space for a fixed bound on venues. Trace on the fills A, B, A, C, C, C, B, A: after three fills the window is A, B, A; the C makes three venues, so the left end drops the first A (still three) and the B, leaving A, C; two more C’s give A, C, C, C, length 4; the B drops the A, leaving C, C, C, B, length 4; the last A drops the three C’s, leaving B, A. The answer is 4, which the brute force confirms here and the chapter’s test confirms against it on random inputs.