배열 A가 있다고 가정합니다. 일부 시작 인덱스에서 일련의 점프를 만들 수 있습니다. 연속으로 위치(1, 3, 5, ...) 점프하는 것을 홀수 점프라고 하고, 시리즈에서 위치(2, 4, 6, ...)로 점프하는 것을 짝수 점프라고 합니다.
이제 인덱스 i에서 다음과 같은 방식으로 인덱스 j(i
-
홀수 점프 동안 A[i] <=A[j] 및 A[j]가 가능한 가장 작은 값이 되도록 인덱스 j로 점프할 수 있습니다. 이러한 인덱스 j가 여러 개 있는 경우 가장 작은 인덱스 j로만 이동할 수 있습니다.
-
짝수 번호 점프 중에 A[i]>=A[j] 및 A[j]가 가능한 가장 큰 값이 되도록 인덱스 j로 점프할 수 있습니다. 이러한 인덱스 j가 여러 개 있는 경우 가장 작은 인덱스 j로만 이동할 수 있습니다.
-
일부 인덱스 i의 경우 법적 점프가 없는 경우일 수 있습니다.
이제 시작 인덱스는 해당 인덱스에서 시작하여 몇 번 점프하여 배열의 끝에 도달할 수 있을 때 good이라고 합니다.
좋은 시작 인덱스의 수를 찾아야 합니다.
따라서 입력이 [10,13,12,14,15]와 같으면 출력은 2가 됩니다. 끝에 도달할 수 있는 두 자리 인덱스 3과 4가 있기 때문입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
렛 :=1
-
n :=A의 크기
-
크기가 n인 배열 nextGreaterEqual을 정의합니다. 이를 -1로 채웁니다.
-
크기가 n인 배열 nextSmallerEqual을 정의합니다. 이를 -1로 채웁니다.
-
하나의 맵 st 정의
-
초기화 i :=n - 1의 경우, i>=0일 때 업데이트(i를 1만큼 감소), −
-
if :=값이 A[i]보다 크지 않은 키-값 쌍
-
nextGreaterEqual[i] :=(it)이 마지막 요소가 아니면 그 값, 그렇지 않으면 -1
-
st의 마지막 요소와 같지 않고 첫 번째 요소가 A[i]와 같으면 -
-
(1씩 증가)
-
-
nextSmallerEqual[i] :=(it)이 첫 번째 요소가 아니면 이전 값, 그렇지 않으면 -1
-
st[A[i]] :=i
-
-
크기가 n x 2인 하나의 2D 배열 v를 정의하고 이를 false로 채웁니다.
-
v[n - 1, 0] =v[n - 1, 1] =참
-
initialize i :=n - 2의 경우 i>=0일 때 업데이트(i를 1만큼 감소), −
-
nextGreaterEqual[i]가 -1과 같지 않으면 -
-
v[i, 1] :=v[nextGreaterEqual[i], 0]
-
-
nextSmallerEqual[i]가 -1과 같지 않으면 -
-
v[i, 0] :=v[nextSmallerEqual[i], 1]
-
-
v[i, 1]이 0이 아니면 -
-
(ret 1 증가)
-
-
-
리턴 렛
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
#include <bits/stdc++.h> using namespace std; class Solution { public: int oddEvenJumps(vector<int>& A){ int ret = 1; int n = A.size(); vector<int> nextGreaterEqual(n, -1); vector<int> nextSmallerEqual(n, -1); map<int, int> st; for (int i = n - 1; i >= 0; i--) { map<int, int>::iterator it = st.lower_bound(A[i]); nextGreaterEqual[i] = (it != st.end()) ? it->second : -1; if (it != st.end() && it->first == A[i]) it++; nextSmallerEqual[i] = it != st.begin() ? prev(it)->second : -1; st[A[i]] = i; } vector<vector<bool> > v(n, vector<bool>(2, false)); v[n - 1][0] = v[n - 1][1] = true; for (int i = n - 2; i >= 0; i--) { if (nextGreaterEqual[i] != -1) { v[i][1] = v[nextGreaterEqual[i]][0]; } if (nextSmallerEqual[i] != -1) { v[i][0] = v[nextSmallerEqual[i]][1]; } if (v[i][1]) ret++; } return ret; } }; main(){ Solution ob; vector<int> v = {10,13,12,14,15}; cout << (ob.oddEvenJumps(v)); }
입력
{10,13,12,14,15}
출력
2