algorithm - 移动最大变量

Question

昨天，我在一次技术面试中被问到以下问题。

假设您在一家新闻机构工作。在每个离散的时间点 t，故事都会中断。有些故事比其他故事更有趣。这种“热度”用自然数 h 表示，数字越大代表新闻报道越热。

给定一个 S 的 n 故事流，你的工作是从最近的 k 个故事中找到 HitTest 门的故事，每一个 t >= k.

到目前为止，一切顺利:这是移动最大值问题(也称为滑动窗口最大值问题)，并且有一个 linear-time algorithm就解决了。

现在问题变得更难了。当然，与新故事相比，旧故事通常不那么热门。令最近故事的年龄 a 为零，并让任何其他故事的年龄比其后续故事的年龄大 1。然后将故事的“改进的热度”定义为 max(0, min(h, k - a))。

这是一个例子:

n = 13, k = 4

S indices:   0   1   2   3   4   5   6   7   8   9  10
S values:    1   3   1   7   1   3   9   3   1   3   1

mov max hot indices:     3   3   3   6   6   6   6   9
mov max hot values:      7   7   7   9   9   9   9   3

mov max imp-hot indices: 3   3   5   6   7   7   9   9
mov max imp-hot values:  4   3   3   4   3   3   3   3

这个问题让我一头雾水。我考虑过在计算最大值之前将索引添加到每个元素，但这给了你一个故事的热度何时每一步都减少 1 的答案，无论它是否达到热度界限。

你能为这个问题找到一个具有次二次(理想情况下:线性)运行时间的算法吗？

Answer 1

我将为涉及双端队列 (deque) 的原始问题绘制一个线性时间解决方案，然后将其扩展到改进的热度而不损失渐近效率。

原始问题:在窗口中保留一个双端队列，其中包含 (1) 比到目前为止 (2) 的所有其他故事更新或更热的故事。在任何给定时间，队列中 HitTest 门的故事都排在最前面。在从后面弹出每个故事直到找到更热门的故事之后，新故事被推到双端队列的后面。故事随着窗外的老化从前面弹出。

例如:

S indices:   0   1   2   3   4   5   6   7   8   9  10
S values:    1   3   1   7   1   3   9   3   1   3   1

deque: (front) [] (back)
push (0, 1)
deque: [(0, 1)]
pop (0, 1) because it's not hotter than (1, 3)
push (1, 3)
deque: [(1, 3)]
push (2, 1)
deque: [(1, 3), (2, 1)]
pop (2, 1) and then (1, 3) because they're not hotter than (3, 7)
push (3, 7)
deque: [(3, 7)]
push (4, 1)
deque: [(3, 7), (4, 1)]
pop (4, 1) because it's not hotter than (5, 3)
push (5, 3)
deque: [(3, 7), (5, 3)]
pop (5, 3) and then (3, 7) because they're not hotter than (6, 9)
push (6, 9)
deque: [(6, 9)]
push (7, 3)
deque: [(6, 9), (7, 3)]
push (8, 1)
deque: [(6, 9), (7, 3), (8, 1)]
pop (8, 1) and (7, 3) because they're not hotter than (9, 3)
push (9, 3)
deque: [(6, 9), (9, 3)]
push (10, 1)
pop (6, 9) because it exited the window
deque: [(9, 3), (10, 1)]

为了处理新问题，我们修改了处理老化故事的方式。我们不是在故事滑出窗口时弹出故事，而是在其改进的热度变得小于或等于它的热度时弹出头条故事。在确定头条新闻时，只需要考虑最近弹出的故事。

在 Python 中:

import collections

Elem = collections.namedtuple('Elem', ('hot', 't'))


def winmaximphot(hots, k):
    q = collections.deque()
    oldtop = 0
    for t, hot in enumerate(hots):
        while q and q[-1].hot <= hot:
            del q[-1]
        q.append(Elem(hot, t))
        while q and q[0].hot >= k - (t - q[0].t) > 0:
            oldtop = k - (t - q[0].t)
            del q[0]
        if t + 1 >= k:
            yield max(oldtop, q[0].hot) if q else oldtop
        oldtop = max(0, oldtop - 1)


print(list(winmaximphot([1, 3, 1, 7, 1, 3, 9, 3, 1, 3, 1], 4)))