Summary
A typical sliding window problem requires the longest or shortest subarray which satisfies certain constraints. The constraint must satisfy a monotonic property: as the right end of the window increases, the left end won’t decrease.
If the constrain is related to maximum or minimum, we could use Monotonic Queues, which are perfect data structures to get the sliding window maximum or minimum.
Details
LC 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
Firstly we should confirm it satisfies the monotonic property. We keep a window [left,right] where left is the leftmost index which keeps the absolute diff constraint.
When right increases, if the current window [left,right+1] breaks the absolute diff constraint, the window [x,right+1] for x in [0,left-1] can’t satisfy the diff contains since the max and min values are always in [left,right], which causes the diff won’t decrease.
When right increases, if the current window [left,right+1] doesn’t break the constraint, left can’t decrease since in the last run, left is the leftmost good index.
Now for every right, we need to get the leftmost left. It could be done by keeping two monotonic queues (one for max, one for min), and increase left until slidingMax-slidingMin<=limit. The current[left,right] is the longest subarray for right.