สมมติว่ามีอาร์เรย์เริ่มต้น arr ทุกวันเราจะสร้างอาร์เรย์ใหม่โดยใช้อาร์เรย์ของวันก่อนหน้า ในวันที่ i เราจะดำเนินการต่อไปนี้บนอาร์เรย์ของวันที่ i-1 เพื่อสร้างอาร์เรย์ของวันที่ i เงื่อนไขมีดังนี้
- ถ้าองค์ประกอบน้อยกว่าค่าติดกันทั้งด้านซ้ายและขวา ให้เพิ่มค่าขององค์ประกอบนั้นขึ้น 1
- ถ้าองค์ประกอบมากกว่าค่าติดกันทั้งด้านซ้ายและขวา ให้ลดค่าขององค์ประกอบนั้นลง 1
- องค์ประกอบแรกและสุดท้ายจะคงที่ไม่เปลี่ยนแปลง
หลังจากผ่านไปหลายวัน อาร์เรย์จะไม่เปลี่ยนแปลงอีกต่อไป ให้หาอาร์เรย์สุดท้ายนั้น ตัวอย่างเช่น หากอาร์เรย์เริ่มต้นคือ [6,2,3,4] ผลลัพธ์จะเป็น [6,3,3,4] ในวันแรก อาร์เรย์จะเปลี่ยนจาก [6,2,3,4] เป็น [6,3,3,4] จากนั้นจะไม่มีการดำเนินการต่อ
ขั้นตอนการแก้ปัญหา
- ถ้าขนาดอาร์เรย์เป็น 2 หรือน้อยกว่า ให้คืนค่าอาร์เรย์
- ตั้งค่า flag := true
- while flag เป็น true
- ตั้งค่า flag := false
- สร้างอาร์เรย์ว่างชื่อ temp และแทรก arr[0] ลงใน temp
- for i ในช่วง 1 ถึงขนาดอาร์เรย์ - 1
- ถ้า arr[i] < arr[i-1] และ arr[i] < arr[i+1] ให้แทรก arr[i] + 1 ลงใน temp และตั้งค่า flag เป็น true
- อื่นๆ ถ้า arr[i] > arr[i-1] และ arr[i] > arr[i+1] ให้แทรก arr[i] - 1 ลงใน temp และตั้งค่า flag := true
- อื่นๆ ให้แทรก arr[i] ลงใน temp
- แทรกองค์ประกอบสุดท้ายของ arr ลงใน temp
- arr := temp
- คืนค่า arr
ตัวอย่าง (C++):
ลองดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
#include <bits/stdc++.h>
using namespace std;
#define push push_back
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i < v.size(); i++){
cout << v[i] << ", ";
}
cout << "]" << endl;
}
class Solution {
public:
vector<int> transformArray(vector<int>& arr) {
if(arr.size() <= 2) return arr;
bool flag = true;
while(flag){
flag = false;
vector<int> temp;
temp.push_back(arr[0]);
for(int i = 1; i < arr.size() - 1; i++){
if(arr[i] < arr[i-1] && arr[i] < arr[i+1]){
temp.push(arr[i] + 1);
flag = true;
}
else if(arr[i] > arr[i-1] && arr[i] > arr[i+1]){
flag = true;
temp.push(arr[i] - 1);
}
else temp.push(arr[i]);
}
temp.push_back(arr[arr.size() - 1]);
arr = temp;
}
return arr;
}
};
int main(){
Solution ob;
vector<int> v = {1,6,3,4,3,5};
print_vector(ob.transformArray(v));
}อินพุต
[1,6,3,4,3,5]
เอาต์พุต
[1,4,4,4,4,5]
