Thay thế phần tử bằng giá trị lớn nhất bên phải C++

Cho mảng A, thay thế mỗi phần tử bằng giá trị lớn nhất ở bên phải của nó. Phần tử cuối thay bằng -1.

Ví dụ

A = [5, 17, 40, 6, 3, 8, 2] → [40, 40, 8, 8, 8, 2, -1]

Thuật toán duyệt ngược (O(n))

1. Khởi tạo max_right = -1
2. Duyệt từ cuối về đầu (i = n-1 → 0):
3. Lưu temp = max_right
4. Cập nhật max_right = max(max_right, arr[i])
5. Gán arr[i] = temp

Chương trình mẫu

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<int> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++)
        cout << v[i] << (i+1<v.size() ? ", " : "");
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        int max_right = -1;
        int n = arr.size();
        for (int i = n - 1; i >= 0; i--) {
            int temp = max_right;
            max_right = max(max_right, arr[i]);
            arr[i] = temp;
        }
        return arr;
    }
};

int main() {
    Solution ob;
    vector<int> c = {5, 17, 40, 6, 3, 8, 2};
    print_vector(ob.replaceElements(c));
    return 0;
}

Kết quả

[40, 40, 8, 8, 8, 2, -1]

Giải thích: Duyệt ngược giữ max_right là max của các phần tử đã duyệt (bên phải). Gán arr[i] = max_right cũ (trước khi cập nhật).

Độ phức tạp: O(n) thời gian, O(1) không gian thêm (sửa tại chỗ).