Number of Subarrays with Bounded Maximum

We are given an array A of positive integers, and two positive integers L and R (L <= R).

给出非负整形数组 A,另给出两个非负整数 L,R(L <= R)。

Return the number of (contiguous, non-empty) subarrays such that the value of the maximum array element in that subarray is at least L and at most R.

返回 A 的子串中最大值在 L 和 R 区间的字符串的数量。

  • L, R  和 A[i] 范围为 [0, 10^9].

  • A 的长度限制在 [1, 50000] 区间内.


解题思路

第一种解法

稍微分析一下规律,如果给出的数组 A 全都在 L 和 R 之间,比如:

当给出的 A 并不那么完美,当遇见不在左右区间的数字,此时便不需叠加下标,只需叠加当前数字距离最远区间数字的距离。
具体还是看代码理解吧,多写点例子,画一画就明白了。

山路元无雨,空翠湿人衣。

Hello world!
文章已创建 197

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部