정수 배열이 있다고 가정합니다. 배열에 있는 각 요소의 가장 가까운 왼쪽 요소와 오른쪽 작은 요소 사이의 최대 절대 차이를 찾아야 합니다. 요소의 오른쪽이나 왼쪽에 더 작은 요소가 없으면 더 작은 요소로 0을 넣습니다.
따라서 입력이 A =[3, 5, 9, 8, 8, 10, 4]와 같으면 출력은 왼쪽 요소 L =[0, 3, 5, 5, 5, 8, 3으로 4가 됩니다. ], 오른쪽 요소 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]:=스택의 최상위 요소
-
-
그렇지 않으면
-
온도[i]:=0
-
-
스택 끝에 A[i] 삽입
-
-
기본 방법에서 다음을 수행하십시오 -
-
n :=A의 크기
-
왼쪽:=크기가 n이고 0으로 채워진 목록
-
right:=크기가 n이고 0으로 채워진 목록
-
left_small_element(A, 왼쪽)
-
left_small_element(역 A, 오른쪽)
-
해상도 :=-1
-
0에서 n 사이의 i에 대해 수행
-
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