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

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

因此，如果输入类似于 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 的大小

  • stack := 一个新的列表

  • 对于 i 从 0 到 n 的范围，执行以下操作

    • 当 stack 不为空且 stack 的顶部元素 >= A[i] 时，执行以下操作

      • 从 stack 中删除最后一个元素

    • 如果 stack 不为空，则

      • temp[i]:= stack 的顶部元素

    • 否则，

      • temp[i]:= 0

    • 将 A[i] 插入到 stack 的末尾

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

  • n := A 的大小

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

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

  • left_small_element(A, left)

  • left_small_element(反转 A, right)

  • res := -1

  • 对于 i 从 0 到 n 的范围，执行以下操作

    • res := 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

更新于: 2020年8月25日

186 次查看

开启你的 职业生涯

通过完成课程获得认证

开始
广告