Nhảy chẵn lẻ trong C++

Cho mảng A. Từ chỉ số bắt đầu, thực hiện chuỗi nhảy. Nhảy thứ 1,3,5... là nhảy lẻ; 2,4,6... là nhảy chẵn. Từ i nhảy đến j (i

• Nhảy lẻ: A[i] ≤ A[j] và A[j] nhỏ nhất có thể. Nếu nhiều j, chọn j nhỏ nhất.
• Nhảy chẵn: A[i] ≥ A[j] và A[j] lớn nhất có thể. Nếu nhiều j, chọn j nhỏ nhất.

Chỉ số tốt nếu từ đó có thể đến cuối mảng. Đếm số chỉ số tốt.

Ví dụ: [10,13,12,14,15] → 2 (chỉ số 3 và 4).

Giải pháp

Tiền xử lý nextGreaterEqual và nextSmallerEqual bằng map (BST):

• Duyệt i từ n-1 xuống 0:
  • nextGreaterEqual[i] = chỉ số j > i nhỏ nhất với A[j] ≥ A[i] (lower_bound)
  • nextSmallerEqual[i] = chỉ số j > i nhỏ nhất với A[j] ≤ A[i] (prev của upper_bound)
  • Chèn A[i]→i vào map
• DP: v[i][0] = có thể đến cuối từ i với nhảy chẵn tiếp theo, v[i][1] = nhảy lẻ tiếp theo
  • v[n-1][0] = v[n-1][1] = true
  • Duyệt i từ n-2 xuống 0:
    • v[i][1] = v[nextGreaterEqual[i]][0] (nếu tồn tại)
    • v[i][0] = v[nextSmallerEqual[i]][1] (nếu tồn tại)
  • Đếm ret = số i với v[i][1] = true

Ví dụ mã C++

#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--) { 
            auto 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; 
    } 
}; 

int main() { 
    Solution ob; 
    vector<int> v = {10,13,12,14,15}; 
    cout << (ob.oddEvenJumps(v)); 
    return 0; 
}

Đầu vào

{10,13,12,14,15}

Đầu ra

2