Giả sử chúng ta có một mảng các số nguyên; chúng ta phải tìm sự khác biệt tuyệt đối lớn nhất giữa phần tử nhỏ hơn bên trái và bên phải gần nhất của mỗi phần tử trong mảng. Nếu không có phần tử nào nhỏ hơn ở phía bên phải hoặc bên trái của bất kỳ phần tử nào thì chúng tôi sẽ đặt số 0 là phần tử nhỏ hơn.
Vì vậy, nếu đầu vào là A =[3, 5, 9, 8, 8, 10, 4], thì đầu ra sẽ là 4 phần tử bên trái L =[0, 3, 5, 5, 5, 8, 3 ], các phần tử bên phải R =[0, 4, 8, 4, 4, 4, 0], chênh lệch tuyệt đối lớn nhất L [i] - R [i] =8 - 4 =4.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Định nghĩa một hàm left_small_element (). Điều này sẽ mất A, tạm thời
-
n:=kích thước của A
-
stack:=một danh sách mới
-
đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện
-
trong khi ngăn xếp không trống và phần tử trên cùng của ngăn xếp> =A [i], do
-
xóa phần tử cuối cùng khỏi ngăn xếp
-
-
nếu ngăn xếp không trống, thì
-
temp [i]:=phần tử trên cùng của ngăn xếp
-
-
nếu không,
-
tạm thời [i]:=0
-
-
chèn A [i] vào cuối ngăn xếp
-
-
Từ phương thức chính, thực hiện như sau -
-
n:=kích thước của A
-
left:=danh sách kích thước n và điền bằng 0
-
right:=danh sách kích thước n và điền bằng 0
-
left_small_element (A, left)
-
left_small_element (đảo ngược A, sang phải)
-
res:=-1
-
đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện
-
res:=tối đa res, | left [i] - right [n-1-i] |
-
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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))
Đầu vào
[3, 5, 9, 8, 8, 10, 4]
Đầu ra
4