배열 번호가 있다고 가정하고 왼쪽과 오른쪽이라고 하는 두 개의 다른 하위 배열로 분할해야 다음과 같이 됩니다. -
-
왼쪽 부분배열의 각 요소는 오른쪽 부분배열의 각 요소보다 작거나 같습니다.
-
왼쪽 및 오른쪽 하위 배열이 비어 있지 않습니다.
-
왼쪽 하위 배열은 가능한 가장 작은 크기를 갖습니다.
이러한 분할 후 왼쪽 길이를 찾아야 합니다.
따라서 입력이 nums =[5,0,3,8,6]과 같으면 왼쪽 배열이 [5,0,3]이고 오른쪽 하위 배열이 [8,6]이 되기 때문에 출력은 3이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
mx :=null, temp :=null, nmx :=null
-
temp2 :=0
-
숫자로 된 각 i에 대해 수행
-
mx가 null과 같으면
-
mx :=나는
-
nmx :=i
-
임시 :=임시2
-
temp2 :=temp2 + 1
-
다음 반복으로 이동
-
-
i>=mx이면
-
temp2 :=temp2 + 1
-
i>nmx이면
-
nmx :=i
-
-
다음 반복으로 이동
-
-
그렇지 않으면
-
임시 :=임시2
-
temp2 :=temp2 + 1
-
mx :=nmx
-
다음 반복으로 이동
-
-
-
반환 온도+1
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(nums):
mx = None
temp = None
nmx = None
temp2 = 0
for i in nums:
if(mx==None):
mx = i
nmx = i
temp = temp2
temp2+=1
continue
if(i>=mx):
temp2+=1
if(i>nmx):
nmx = i
continue
else:
temp = temp2
temp2+=1
mx = nmx
continue
return temp+1
nums = [5,0,3,8,6]
print(solve(nums)) 입력
[5,0,3,8,6]
출력
3