[Leetcode][915] Partition Array into Disjoint Intervals

문제 : https://leetcode.com/problems/partition-array-into-disjoint-intervals/

---

배열 A를 뒤에서부터 탐색하면서 [탐색중인 인덱스, 끝] 에 포함되는 배열 요소들의 최소값을 저장하는 배열을 만든다.

최소값을 저장하는 배열을 만들었다면 이번에는 배열 A를 앞에서부터 탐색하면서 [시작 ~ 탐색중인 인덱스]의 요소들의 최대값을 구한다.

탐색중인 인덱스를 ind라 하였을 때 만약 ind까지 구한 최대값이 [ind, 끝] 범위의 최소값보다 작다면 정답이 될 수 있는 경우이다.

ex) [5, 0, 3, 8, 6] 

-> [5, 0] [3, 8, 6] 으로 나뉜다고 보면 ind는 1이 되고 ind까지의 최대값은 5, ind ~ 끝 범위의 최소값은 3이 되므로 정답이 될 수 없다. (5 > 3)

-> [5, 0, 3] [8, 6] 으로 나뉜다고 보면 ind는 2가 되고 ind까지의 최대값은 5, ind ~ 끝 범위의 최소값은 6이 되므로 정답이 될 수 있다. (5 < 6)

정답이 될 수 있는 경우의 ind를 구했을 때 정답은 왼쪽 배열의 크기이므로 ind + 1이 정답이 된다.(인덱스는 0부터 시작되므로 크기는 + 1)

배열 A크기를 N이라했을 때, 시간복잡도는 O(N).

---

소스코드 : https://gist.github.com/fpdjsns/906064f24f55e7ad159cd45b4fc64049