크기 N짜리 unsigned int 배열 arr이 주어지고
거기서 (R - L - 1) * min( arr[R], arr[L] )의 최댓값을 찾는다
O(N^2) 쓰면 시간초과, 최대 O(N * (logN)^2) 까지 ㅇㅋ
이거랑 비슷한 1725번 히스토그램은 세그먼트 트리로 구간 [L,R] 내에서 arr의 최솟값 찾아서 풀었는데
얘는 구간이 아니라서 세그트리 풀이가 안먹힐거같아요
그래도 비슷한 문제니 플5급되려나요
거기서 (R - L - 1) * min( arr[R], arr[L] )의 최댓값을 찾는다
O(N^2) 쓰면 시간초과, 최대 O(N * (logN)^2) 까지 ㅇㅋ
이거랑 비슷한 1725번 히스토그램은 세그먼트 트리로 구간 [L,R] 내에서 arr의 최솟값 찾아서 풀었는데
얘는 구간이 아니라서 세그트리 풀이가 안먹힐거같아요
그래도 비슷한 문제니 플5급되려나요
스위핑으로 풀면 됨. arr에서 가장 작은 값의 인덱스를 l로 잡으면 l과 가장 멀리 떨어진 인덱스를 r로 잡는 게 최적이야. 그다음엔 두 번째로 작은 인덱스를 l로 잡고 r을 최대한 멀리 잡아야 하는데, l과 r 사이에 이전에 봤던 "arr에서 가장 작은 값"이 포함되면 안돼. 이전에 봤던 값들을 tree set에 저장해뒀다면 가장 멀리 떨어진 곳을 로그
시간에 찾을 수 있으니 nlogn에 풀릴듯? 풀이에 오류 있으면 지적해줘
min(arr[R],arr[L])=arr[L]인 경우에 대해 생각했을 때 arr[R]>=arr[L]이면서 제일 오른쪽으로 가는 R을 찾으면 되니까 최댓값 세그로 이러한 R을 찾는 방식으로 풀 수 있지 않을까요 세그써서 플5정도 되겠네여 근데 R-L+1을 R-L-1로 잘못 쓰신 건가요?
뒷북이긴 한데 l=1, r=N로 시작해서 arr[l] < arr[r]이면 l 증가, 아니면 r 증가하면서 투포인터 돌리며 최대값 갱신하면 됨
arr[l] < arr[r]이면 arr[l]에 대해 현재의 r-l이 최대라서 l을 더 볼 필요가 없고, 반대 경우도 마찬가지.