Chuyển đổi mảng trong C++

Giả sử có một mảng ban đầu arr, mỗi ngày ta tạo một mảng mới dựa trên mảng của ngày trước. Ở ngày thứ i, ta thực hiện các phép toán sau trên mảng ngày i-1 để tạo mảng ngày i. Các điều kiện như sau:

• Nếu một phần tử nhỏ hơn cả hai giá trị liền kề trái và phải, phần tử này được tăng lên 1.
• Nếu một phần tử lớn hơn cả hai giá trị liền kề trái và phải, phần tử này được giảm đi 1.
• Phần tử đầu tiên và cuối cùng giữ nguyên.

Sau một số ngày, mảng không còn thay đổi. Hãy tìm mảng cuối cùng đó. Ví dụ, nếu mảng ban đầu là [6,2,3,4] thì đầu ra là [6,3,3,4]. Ở ngày đầu tiên, mảng thay đổi từ [6,2,3,4] thành [6,3,3,4], sau đó không còn phép toán nào được thực hiện.

Để giải quyết, ta làm theo các bước:

• Nếu kích thước mảng ≤ 2, trả về mảng đó
• Đặt flag := true
• Trong khi flag là true:
  • Đặt flag := false
  • Tạo mảng rỗng temp, thêm arr[0] vào temp
  • Với i từ 1 đến kích thước mảng - 2:
    • Nếu arr[i] < arr[i-1] và arr[i] < arr[i+1], thêm arr[i]+1 vào temp, đặt flag = true
    • Ngược lại nếu arr[i] > arr[i-1] và arr[i] > arr[i+1], thêm arr[i]-1 vào temp, đặt flag = true
    • Ngược lại thêm arr[i] vào temp
  • Thêm phần tử cuối của arr vào temp
  • arr := temp
• Trả về arr

Ví dụ (C++):

Xem triển khai sau để hiểu rõ hơn:

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

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> 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)); 
    return 0;
}

Đầu vào

[1,6,3,4,3,5]

Đầu ra

[1,4,4,4,4,5]