algorithm - 计算 a[i] 最右边或最左边且最大的段

Question

你得到一个包含N整数的数组，你必须回答K查询。每个查询都包含一个整数X，它是数组（基于 1 的索引）元素的索引。
为每个查询计算以下内容：

The number of segments containing the index X as the leftmost or the 
rightmost element and the number at the index `X` is `>=` each element
of that segment.

段形成示例：
您有 array {1, 2, 3}。可能的段3是[2,3]和[1,2,3]和[3]。
2的可能部分是[2]，[1,2]
我通过蛮力得到了解决方案。最坏情况的时间复杂度是O(n * k)

Input: Array[] = {4,2,1,3}, Queries[] = {1,4}
Output:  
4  
3

Explanation: 
For first query 1 all possible valid segments are [4], [4,2] , [4,2,1] and [4,2,1,3] 
hence answer is 4.  
For second query 4 all possible valid segments are [3], [1,3] and [2,1,3]
hence answer is 3.

标签： algorithm

Answer 1

让我们关注最左边，因为最右边是镜像。

对于每一个X，我们等价地想计算之后a[X]有多少个连续的条目小于或等于a[X]。有一个技巧可以在线性时间内使用堆栈来做到这一点。我们从左到右扫描数组并使用堆栈来记住哪些Xs 仍在累积元素。关键属性是a堆栈元素对应的值不会递减，因此一旦堆栈顶部的元素还没有完成，它下面的元素也不会减少。

例如，假设输入是

  X : 1,2,3,4,5,6,7,8
a[X]: 3,1,4,1,5,9,2,6

从左到右扫描阵列。

stack is initially empty
a[1] = 3
push 1, stack is 1
a[2] = 1
don't pop 1 since a[1] = 3 ≥ 1 = a[2]
push 2, stack is 1,2
a[3] = 4
pop 2 since a[2] = 1 < 4 = a[3]; the answer for X=2 is 3 - 2 = 1
pop 1 since a[1] = 3 < 4 = a[3]; the answer for X=1 is 3 - 1 = 2
push 3, stack is 3
a[4] = 1
don't pop 3 since a[3] = 4 ≥ 1 = a[4]
push 4, stack is 3,4
a[5] = 5
pop 4 since a[4] = 1 < 5 = a[5]; the answer for X=4 is 5 - 4 = 1
pop 3 since a[3] = 4 < 5 = a[5]; the answer for X=3 is 5 - 3 = 2
push 5, stack is 5
a[6] = 9
pop 5 since a[5] = 5 < 9 = a[6]; the answer for X=5 is 6 - 5 = 1
push 6, stack is 6
a[7] = 2
don't pop 6 since a[6] = 9 ≥ 2 = a[7]
push 7, stack is 6,7
a[8] = 6
pop 7 since a[7] = 2 < 6 = a[8]; the answer for X=7 is 8 - 7 = 1
don't pop 6 since a[6] = 9 ≥ 6 = a[8]
push 8, stack is 6,8

然后最后我们弹出所有剩下的东西。

pop 8; the answer for X=8 is 9 - 8 = 1
pop 6; the answer for X=6 is 9 - 6 = 3

在 Python 中：

def rightward(lst):
    counts = [0] * len(lst)
    stack = []
    for i, x in enumerate(lst):
        while stack and lst[stack[-1]] < x:
            counts[stack[-1]] = i - stack[-1]
            del stack[-1]
        stack.append(i)
    while stack:
        counts[stack[-1]] = len(lst) - stack[-1]
        del stack[-1]
    return counts


def intervals(lst):
    return list(map(lambda l, r: l + r - 1, rightward(lst[::-1])[::-1], rightward(lst)))


print(intervals([3, 1, 4, 1, 5, 9, 2, 6]))