移动最大变量

Question

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

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

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

到目前为止，一切顺利：这是移动最大值问题（也称为滑动 window 最大值问题），并且有一个 linear-time algorithm 可以解决它。

现在问题变得更难了。当然，与新故事相比，旧故事通常不那么热门。让最近故事的年龄 a 为零，并让任何其他故事的年龄比其后续故事的年龄大 1。故事的 "improved hotness" 定义为 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

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

你能用次二次（理想情况下：线性）运行时间找到解决这个问题的算法吗？

Answer 1

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

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

年龄的增长从前面弹出

例如：

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)]

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

在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)))

Answer 2

思路如下：对于每条突发新闻，经过k-h步后，都将击败之前所有的新闻。意思是k==30和新闻热度h==28，这条新闻在2步之后会比之前所有的新闻都热。让我们保留下一个新闻最热门的所有时刻。在步骤 i 中，我们得到当前新闻将击败所有先前新闻的时刻等于 i+k-h。所以我们将有这样的对象序列 {news_date | news_beats_all_previous_ones_date}，按 news_beats_all_previous_ones_date:

递增

{i1 | i1+k-h} {i3 | i3+k-h} {i4 | i4+k-h} {i7 | i7+k-h} {i8 | i8+k-h}

在当前步骤我们得到 i9+k-h，我们将它添加到这个列表的末尾，删除所有更大的值（因为序列增加这很容易）。一旦第一个元素的 news_beats_all_previous_ones_date 等于当前日期 (i)，这个消息就成为滑动 window 查询的答案，我们从序列中删除这个项目。因此，您需要一个能够添加到末尾并从开头和结尾删除的数据结构。这是Deque。解的时间复杂度为O(n).

移动最大变量

Moving maximum variant

algorithm

max

moving-average