移动最大变量

Question

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

想象一下，你正在为一家新闻机构工作。在每个离散的时间点t，一个故事都会破裂。有些故事比其他的更有趣。这种“热度”被表示为一个自然数h，较大的数字表示更热门的新闻故事。

给定一系列S的n故事，您的工作就是从每个t >= k的最新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

我对这个问题完全不知所措。我想过在计算最大值之前将索引添加到每个元素，但这给了您一个答案，即当故事的热度在每一步都减少一个时，无论它是否达到热度界限。

你能找到一个算法来解决这个问题，运行时间是次二次(理想情况下:线性)吗？