难度: Medium
Submission
运行时间: 164 ms
内存: 33.3 MB
from typing import List
class Solution:
def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [1] * n # 初始化结果数组，每个元素的默认值为 1
stack = [] # 用于存储元素索引的栈
# 遍历数组，维护一个递减栈
for i in range(n):
while stack and nums[i] > nums[stack[-1]]:
# 弹出栈顶元素，并更新结果数组中对应位置的值
index = stack.pop()
ans[index] = i if not stack else i - stack[-1] - 1
stack.append(i)
# 处理栈中剩余的元素
while stack:
index = stack.pop()
ans[index] = n if not stack else n - stack[-1] - 1
return ans
Explain
此题解的核心思路是利用一个单调递减栈来寻找每个元素作为最大值时的最大范围。遍历输入数组，对于每个元素，如果当前元素大于栈顶元素，则栈顶元素无法继续维持其为最大值的状态，需要从栈中移除，并更新结果数组中该元素的最大范围。如果栈为空，则表示当前元素左边没有更大的元素，其范围可以扩展到数组起始；如果栈不为空，则当前元素的范围是从栈顶元素的下一个位置到当前元素的位置。最后，遍历结束后，栈中剩余的元素表示它们的范围可以扩展到数组末尾。
时间复杂度: O(n)
空间复杂度: O(n)
python
from typing import List
class Solution:
def maximumLengthOfRanges(self, nums: List[int]) -> List[int]:
n = len(nums) # 数组的长度
ans = [1] * n # 初始化结果数组，每个元素的默认值为 1
stack = [] # 用于存储元素索引的栈
# 遍历数组，维护一个递减栈
for i in range(n):
while stack and nums[i] > nums[stack[-1]]:
# 弹出栈顶元素，并更新结果数组中对应位置的值
index = stack.pop()
ans[index] = i if not stack else i - stack[-1] - 1
stack.append(i) # 将当前元素索引压入栈
# 处理栈中剩余的元素
while stack:
index = stack.pop()
ans[index] = n if not stack else n - stack[-1] - 1 # 更新范围至数组末尾
return ans # 返回结果数组
Explore
单调递减栈的选择是为了有效地处理和记录数组中每个元素作为最大值时能够扩展的最大范围。这种栈结构能快速找到一个元素左边和右边第一个比它小的元素，因此可以直接确定该元素的有效范围。使用单调递减栈可以在一次遍历中解决问题，保证时间复杂度为 O(n)，这是其他数据结构（如队列或普通列表）难以实现的。
当一个元素被弹出栈时，表示遇到了一个比栈顶元素大的新元素，这个新元素的索引是当前遍历到的索引。栈顶元素的右边界即为新元素的索引减一。如果栈为空，说明没有左边界，该元素可以扩展到数组的起始；如果栈不为空，栈顶元素的索引加一就是左边界。因此，被弹出元素的范围可以通过当前索引与左边界之间的差值来确定。
如果数组中存在重复元素，算法的处理方式不会直接受到影响因为单调递减栈在遇到重复元素时，由于重复元素不大于栈顶元素，它们会被继续压入栈中。然而，在计算范围时，重复元素会导致它们的范围可能不会立即更新，直到遇到一个更大的元素。这可能导致多个相同的元素有相同的最大范围值。
在算法最后处理剩余在栈中的元素时，这些元素的右边没有出现比它们更大的元素，因此它们的右边界是数组的末尾。栈中的每个元素都可以扩展到数组的末尾，但是需要减去左边界（即栈中前一个元素的索引加一）。因此，最大范围的计算公式是 `n - stack[-1] - 1`，其中 `n` 是数组的长度，`stack[-1]` 是当前元素左边第一个元素的索引。