ปัญหา
ได้รับอาร์เรย์ A ต้องแทนที่ทุกองค์ประกอบด้วยค่าสูงสุดทางด้านขวาของมัน และตัวสุดท้ายแทนด้วย -1 เช่น A = [5, 17, 40, 6, 3, 8, 2] → [40, 40, 8, 8, 8, 2, -1]
วิธีแก้
- อ่านอาร์เรย์จากขวาไปซ้าย
- กำหนด e = -1
- ลูป i = n-1 ถึง 0:
- temp = e
- e = max(e, arr[i])
- arr[i] = temp
- คืนค่า arr
ตัวอย่างโค้ด
#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] << ", ";
}
cout << "]" << endl;
}
class Solution {
public:
vector<int> replaceElements(vector<int>& arr) {
int rep = -1;
int n = arr.size();
for (int i = n - 1; i >= 0; i--) {
int temp = rep;
rep = max(rep, 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));
}
อินพุต
[5, 17, 40, 6, 3, 8, 2]
เอาต์พุต
[40, 40, 8, 8, 8, 2, -1]
คำอธิบาย
อัลกอริทึม O(n) Single Pass จากขวาไปซ้าย เก็บค่าสูงสุดที่เจอมาในตัวแปร rep แต่ละรอบเก็บค่า rep เก่า (ซึ่งคือ max ทางขวา) ลง arr[i] แล้วอัปเดต rep = max(rep, arr[i] เดิม)
