좌는 작고 우는 큰 배열 내의 숫자들 찾기(min/max preprocessing) Q

배열 내의 어느 숫자에 대해 그 왼쪽의 숫자들은 더 작고, 오른쪽의 숫자들은 더 큰 숫자들을 찾아보자.

BST 2개를 만들어서 서로 주고 받는다 >> O(NlogN)

저번에 사용했던 min(max) 값 추적할 수 있는 스택을 사용하면..!!

O(N) 알고리즘을 얻을 수 있다.

재귀적으로 해결 가능하다고 합니다

FindElement(int[] arr, int MaxTillNow, int currentIndex)
{
	if(currentIndex == 0)
	{
		return FindElement(arr, arr[currentIndex], currentIndex + 1);
	}
	if(currentIndex == arr.Length-1)
	{
		return arr[currentIndex];
	}
	int minTillNow = FindElement(arr, Math.Max(MaxTillNow, arr[currentIndex]), currentIndex + 1)
	if(arr[currentIndex] > MaxTillNow && arr[currentIndex] < minTillNow)
	{
		Console.WriteLine(arr[currentIndex]);
	}
	return Math.Min(minTillNow, arr[currentIndex]);
}

https://www.careercup.com/question?id=5738269695279104

다시 생각해 보니 쉬운 문제기도 하네.

각 점에 대해 그 점까지의 min과 max 값을 계산할 수 있으니까, 그걸 preprocessing 해서, 값이 맞으면 출력하는 방식으로 하면 O(N)이 되겠다.

각 점까지의 min과 max preprocessing은 제법 신박하네.