在 Python 中查找左侧和右侧最近较小元素之间的最大差异

pythonserver side programmingprogramming更新于 2025/10/10 15:08:17

假设我们有一个整数数组;我们必须找到数组中每个元素的左侧和右侧最近较小元素之间的最大绝对差异。如果任何元素的右侧或左侧都没有较小的元素,那么我们将零作为较小的元素。

因此,如果输入为 A = [3, 5, 9, 8, 8, 10, 4],则输出将为 4,因为左元素 L = [0, 3, 5, 5, 5, 8, 3],右元素 R = [0, 4, 8, 4, 4, 4, 0],最大绝对差 L[i] - R[i] = 8 - 4 = 4。

为了解决这个问题,我们将遵循以下步骤 −

  • 定义一个函数 left_small_element() 。这将需要 A,temp

  • n := A 的大小

  • 堆栈 := 一个新列表

  • 对于范围为 0 到 n 的 i,执行

    • 当堆栈不为空且堆栈顶部元素 >= A[i] 时,执行

      • 从堆栈中删除最后一个元素

    • 如果堆栈不为空,则

      • temp[i]:= 堆栈顶部元素

    • 否则,

      • temp[i]:= 0

    • 插入A[i] 在堆栈末尾

  • 从主方法中,执行以下操作 −

  • n := A 的大小

  • left:= 大小为 n 的列表并用 0 填充

  • right:= 大小为 n 的列表并用 0 填充

  • left_small_element(A, left)

  • left_small_element(reversed A, right)

  • res := -1

  • 对于范围为 0 到 n 的 i,执行

    • res := maximum of res, |left[i] - right[n-1-i]|

示例

让我们看看下面的实现以便更好地理解 −

def left_small_element(A, temp):
   n = len(A)
   stack = []
   for i in range(n):
      while(stack != [] and stack[len(stack)-1] >= A[i]):
         stack.pop()
      if(stack != []):
         temp[i]=stack[len(stack)-1]
      else:
         temp[i]=0
      stack.append(A[i])
def find_maximum_difference(A):
   n = len(A)
   left=[0]*n
   right=[0]*n
   left_small_element(A, left)
   left_small_element(A[::-1], right)
   res = -1
   for i in range(n):
      res = max(res, abs(left[i] - right[n-1-i]))
   return res
A = [3, 5, 9, 8, 8, 10, 4]
print(find_maximum_difference(A))

输入

[3, 5, 9, 8, 8, 10, 4]

输出

4

相关文章


有用资源