本文共 1276 字，大约阅读时间需要 4 分钟。
为了解决这个问题，我们需要找出给定整数数组中的坡的最大宽度。坡是元组 (i, j)，其中 i < j 且 A[i] ≤ A[j]。坡的宽度为 j - i。我们的目标是找出这样的坡的最大宽度，如果不存在则返回 0。
为了高效地解决这个问题，我们可以使用单调栈的方法。具体步骤如下：
right 来记录每个元素右侧满足条件的最大索引。right 数组，计算每个元素右侧最大索引与当前索引的差值，记录最大的宽度。这种方法的时间复杂度为 O(n)，因为每个元素被弹出栈的次数最多为一次。
class Solution: def maxwidthramp(self, A): n = len(A) if n == 0: return 0 right = [-1] * n stack = [] for i in range(n-1, -1, -1): while stack and stack[-1][0] < A[i]: stack.pop() if stack: right[i] = stack[-1][1] stack.append((A[i], i)) max_width = 0 for i in range(n): if right[i] != -1: current = right[i] - i if current > max_width: max_width = current return max_width
right，初始值为 -1，用于记录每个元素右侧的最大索引。栈用于记录潜在的右侧元素索引。right 数组：在处理完每个元素后，如果栈不为空，栈顶元素就是当前元素右侧的最大索引，我们记录在 right 数组中。right 数组，计算每个元素右侧最大索引与当前索引的差值，记录最大的宽度。这种方法确保了我们在 O(n) 时间内高效地找到最大宽度的坡。
转载地址：http://qpki.baihongyu.com/