증가하는 세개의 인덱스를 O(N)에 찾기

아예 랜덤하게 하나씩 뽑는것도 재밌을 듯. 그리고 나오는게 현재 인덱스들과 어떻게 구성되는지 비교하고 맞출 수 있으면 리턴.

아니면 앞에서부터 순회해야겠지.

현재 처음이야. 다음게 더 작아. 그럼 그걸 처음으로 잡아. 다음게 더 커. 그러면 그게 다음꺼야. 그리고 작은게 나오면 .. 이런식으로는 서로 떨어진 경우를 찾을 수 없다.

자명한 해는 소팅하는 방법.. O(NlogN)

랜덤하게 하나를 뽑는다. 

5 9 이렇게 두개 뽑았는데 중간의 더 작은값이면 버리고.. 아 근데 이것도 결국에는 그걸 못찾고 지나치겠다.

해싱이 답인거같다 O(N) 뽑으려면

해싱해가면서 수를 기록한다.

아니면 프리프로세싱..!!

어 프리프로세싱 되겠다.

오른쪽에 자신보다 큰게 있는가?

왼쪽에 자신보다 작은게 있는가?

 == 왼쪽의 max가 자신보다 큰가?

 == 오른쪽의 min이 자신보다 작은가?

3 2 5 4 1

x x o o x

o o o o x

oo인 점이 있으니 true. 아마 두번째 프로세싱 만들면서 바로 발견가능할듯 .. !!!

아 근데 이렇게도 생각가능한데. 저런게 단 한개도 없다는 뜻은, 무조건 단조감소한다는 뜻이잖아.

..!! 띠용 !!

아 근데 "인덱스"를 찾아야 해서, 결국에는 위 방법이 될듯. 안된다는거는 확인해도 되면 그 점을 찾기는 쉽지 않아서 .. !!

vector<int> findthree(vector<int> & data){

// error cases

if(data.size()<3) return vector<int>();

// make preprocess array

vector<int> maxbuffer(data.size(),-1);

int max = data[0];

for(int i = 1; i < data.size() ; i++){

if(max<data[i]) max = data[i];

maxbuffer[i] = max;

}

// go through to track min and return

int min = data[data.size()-1];

for(int i = data.size()-2; i>= 0 ; i--){

if(min>data[i]) min = data[i];

// check if terminates

if(maxbuffer[i]<data[i]&&data[i]<min){

vector<int> ret = {maxbuffer[i], data[i], min};

return ret;

}

}

// not exist

return vector<int> ();

}

time complexity : O(N)

space complexity : O(N)

--