Leetcode 239: Slide window maximum (series 4 of 10)

June 18, 2018

Introduction

It is time for me to calm down and play with one algorithm with more detail.

Here is the discussion I like to study. And here is the blog I like to read and write down my study notes.

I just quickly copy the statement from the above blog:

Given an array of element a₀, a₁, a₂,..., and queries Q(i, i + L) which means "find the minimum element in a_i, a_i+1, a_i+L". How can we answer such queries efficiently?

We can have an O(nlogn) complexity by using a minimum priority queue, RB tree, or a binary tree representation of multiset, but there in this setting we can implement a data structure called monotonic queue which only requires O(n) in construction. The implementation of this data structure requires a deque.