题目描述
现给定一个由 不同 整数构成的 0 索引数组 nums
。
我们用以下方式定义与 nums
长度相同的 0 索引数组 ans
:
ans[i]
是子数组 nums[l..r]
的 最大 长度,该子数组中的最大元素等于 nums[i]
。
返回数组 ans
。
注意,子数组 是数组的连续部分。
示例 1:
输入:nums = [1,5,4,3,6]
输出:[1,4,2,1,5]
解释:对于 nums[0],最长的子数组,其中最大值为 1,是 nums[0..0],所以 ans[0] = 1。
对于 nums[1],最长的子数组,是 nums[0..3],其中最大值为 5,所以 ans[1] = 4。
对于 nums[2],最长的子数组,是 nums[2..3],其中最大值为 4,所以 ans[2] = 2。
对于 nums[3],最长的子数组,是 nums[3..3],其中最大值为 3,所以 ans[3] = 1。
对于 nums[4],最长的子数组,是 nums[0..4],其中最大值为 6,所以 ans[4] = 5。
示例 2:
输入:nums = [1,2,3,4,5]
输出:[1,2,3,4,5]
解释:对于 nums[i],最长的子数组,是 nums[0..i],其中最大值与 nums[i] 相等,所以 ans[i] = i + 1。
提示:
1 <= nums.length <= 105
1 <= nums[i] <= 105
- 所有
nums
中的元素都是不重复的。
解法
方法一:单调栈
本题属于单调栈的模板题,我们只需要利用单调栈,求出每个元素 $nums[i]$ 左边和右边第一个比它大的元素的位置,分别记为 $left[i]$ 和 $right[i]$,那么 $nums[i]$ 作为最大值的区间长度就是 $right[i] - left[i] - 1$。
时间复杂度 $O(n)$,空间复杂度 $O(n)$。其中 $n$ 为数组长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | class Solution:
def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:
n = len(nums)
left = [-1] * n
right = [n] * n
stk = []
for i, x in enumerate(nums):
while stk and nums[stk[-1]] <= x:
stk.pop()
if stk:
left[i] = stk[-1]
stk.append(i)
stk = []
for i in range(n - 1, -1, -1):
while stk and nums[stk[-1]] <= nums[i]:
stk.pop()
if stk:
right[i] = stk[-1]
stk.append(i)
return [r - l - 1 for l, r in zip(left, right)]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 | class Solution {
public int[] maximumLengthOfRanges(int[] nums) {
int n = nums.length;
int[] left = new int[n];
int[] right = new int[n];
Arrays.fill(left, -1);
Arrays.fill(right, n);
Deque<Integer> stk = new ArrayDeque<>();
for (int i = 0; i < n; ++i) {
while (!stk.isEmpty() && nums[stk.peek()] <= nums[i]) {
stk.pop();
}
if (!stk.isEmpty()) {
left[i] = stk.peek();
}
stk.push(i);
}
stk.clear();
for (int i = n - 1; i >= 0; --i) {
while (!stk.isEmpty() && nums[stk.peek()] <= nums[i]) {
stk.pop();
}
if (!stk.isEmpty()) {
right[i] = stk.peek();
}
stk.push(i);
}
int[] ans = new int[n];
for (int i = 0; i < n; ++i) {
ans[i] = right[i] - left[i] - 1;
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | class Solution {
public:
vector<int> maximumLengthOfRanges(vector<int>& nums) {
int n = nums.size();
vector<int> left(n, -1);
vector<int> right(n, n);
stack<int> stk;
for (int i = 0; i < n; ++i) {
while (!stk.empty() && nums[stk.top()] <= nums[i]) {
stk.pop();
}
if (!stk.empty()) {
left[i] = stk.top();
}
stk.push(i);
}
stk = stack<int>();
for (int i = n - 1; ~i; --i) {
while (!stk.empty() && nums[stk.top()] <= nums[i]) {
stk.pop();
}
if (!stk.empty()) {
right[i] = stk.top();
}
stk.push(i);
}
vector<int> ans(n);
for (int i = 0; i < n; ++i) {
ans[i] = right[i] - left[i] - 1;
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 | func maximumLengthOfRanges(nums []int) []int {
n := len(nums)
left := make([]int, n)
right := make([]int, n)
for i := range left {
left[i] = -1
right[i] = n
}
stk := []int{}
for i, x := range nums {
for len(stk) > 0 && nums[stk[len(stk)-1]] <= x {
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
left[i] = stk[len(stk)-1]
}
stk = append(stk, i)
}
stk = []int{}
for i := n - 1; i >= 0; i-- {
x := nums[i]
for len(stk) > 0 && nums[stk[len(stk)-1]] <= x {
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
right[i] = stk[len(stk)-1]
}
stk = append(stk, i)
}
ans := make([]int, n)
for i := range ans {
ans[i] = right[i] - left[i] - 1
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | function maximumLengthOfRanges(nums: number[]): number[] {
const n = nums.length;
const left: number[] = Array(n).fill(-1);
const right: number[] = Array(n).fill(n);
const stk: number[] = [];
for (let i = 0; i < n; ++i) {
while (stk.length && nums[stk.at(-1)] <= nums[i]) {
stk.pop();
}
if (stk.length) {
left[i] = stk.at(-1);
}
stk.push(i);
}
stk.length = 0;
for (let i = n - 1; i >= 0; --i) {
while (stk.length && nums[stk.at(-1)] <= nums[i]) {
stk.pop();
}
if (stk.length) {
right[i] = stk.at(-1);
}
stk.push(i);
}
return left.map((l, i) => right[i] - l - 1);
}
|