Solving road trip problem in linear time Consider the following problem:


  You are on a road trip, and there are $n$ cities along a road, labeled
  $1$ to $n$. Conveniently, these cities all lie on a single road, and
  the distance between two adjacent cities is one mile. We are currently
  at city $1$, and would like to drive to city $n$. Each day, we can
  drive at most $k$ miles, before we sleep for the night. We pay $a_i$
  for lodging at the city located at mile $i$. Each lodging cost is a
  positive number. Given that we can spend an arbitrary number of days
  on the road trip, determine a plan of driving to minimize lodging
  costs.
  
  Input: An integer $k$, and a length $n$ array of positive integers
  $a_1,...,a_n$.
  
  Output: The minimum lodging cost to complete the road trip starting
  from city 1 and ending at city n.


The most trivial way of solving this problem is to adapt the well-known dynamic programming algorithm for computing the longest increasing subsequence of an array. This requires $n$ iterations and at each iteration, we must compute the minimum of the previous $k$ values, due to the restriction on distance driven per day. This yields an algorithm of time complexity $O(nk)$.

I'm wondering...is there a way to solve this problem in only $O(n)$ time? My intuition is telling me that there is a way to not have to check $k$ prior values at each iteration. Does anyone have an idea?
This problem can be solved in $O(n)$ time, using a min-queue. We can build a data structure that has enqueue, dequeue and get-min operations that all work in amortized $O(1)$ time (rather than $\Omega(\log n)$ time as greybeard seems to think).

Building a min-stack (pop, push, get-min) that does these operations in $O(1)$ time is easy (keep track of the previous minimum in a separate stack when the minimum changes due to a push, so that we can use this secondary stack to restore the previous minimum when the current minimum gets popped). To build a min-queue, we can use the classical construction that builds a queue (with amortised $O(1)$ operations) from two stacks.

The $O(nk)$ dynamic programming algorithm can be modified using the min-queue to run in $O(n)$ time.