Monday, June 18, 2018

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 a0, a1, a2,..., and queries Q(i, i + L) which means "find the minimum element in ai, ai+1, ai+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.


No comments:

Post a Comment