计算A [i]最右或最左且最大的段 [英] Count segments where A[i] is rightmost or leftmost and is max

问题描述

将为您提供一个包含 N 个整数的数组，并且您必须回答 K 个查询.每个查询包含一个整数 X ，它是数组(基于1的索引)元素的索引.
为每个查询计算以下内容:

You are given an array containing N integers and you have to answer K queries. Each query contains an integer X which is the index of the (1 based index) element of the array.
Calculate the following for each query:

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.

段形成示例:
您具有数组 {1、2、3} . 3 的可能段是 [2,3] 和 [1,2,3] 和 [3] .
2的可能段是 [2] 和 [1,2]
我用蛮力解决了.最糟糕的情况是时间复杂度是 O(n * k)

Segment formation example:
You have array {1, 2, 3}. The possible segments for 3 are [2,3] and [1,2,3] and [3].
The possible segments for 2 are [2] and [1,2]
I got solution by brute force. Worst case Time Complexity is 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.

推荐答案

在 O(n)中预处理两个数组，其中元素是原始元素中每个下一个较大元素的索引数组(一个在右边，一个在左边).然后在 O(1)中回答每个查询.

Preprocess two arrays in O(n), where the elements are the indexes of the next larger element for each element in the original array (one to the right and one to the left). Then answer each query in O(1).

这篇关于计算A [i]最右或最左且最大的段的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！