Leetcode - Array Transformation

https://leetcode.com/problems/array-transformation/

Given an initial array arr, every day you produce a new array using the array of the previous day.

On the i-th day, you do the following operations on the array of day i-1 to produce the array of day i:

1. If an element is smaller than both its left neighbor and its right neighbor, then this element is incremented.
2. If an element is bigger than both its left neighbor and its right neighbor, then this element is decremented.
3. The first and last elements never change.

After some days, the array does not change. Return that final array.

Input: arr = [1,6,3,4,3,5]
Output: [1,4,4,4,4,5]
Explanation: 
On the first day, the array is changed from [1,6,3,4,3,5] to [1,5,4,3,4,5].
On the second day, the array is changed from [1,5,4,3,4,5] to [1,4,4,4,4,5].
No more operations can be done to this array.

The most tricky thing is when finding element should be updated, it can't be updated immediately. Otherwise, it will affect next round of calculations. Use array to track the positions which should be updated.

func transformArray(arr []int) []int {
    update := true
    
    for update {
        update = false
        increment := []int{}
        decrement := []int{}
        for i := 1; i < len(arr) - 1; i++ {
            if arr[i] < arr[i-1] && arr[i] < arr[i+1] {
                update = true
                increment = append(increment, i)
            }
            if arr[i] > arr[i-1] && arr[i] > arr[i+1] {
                update = true
                decrement = append(decrement, i)
            }
        }
        for _, i := range increment {
            arr[i]++
        }
        for _, i := range decrement {
            arr[i]--
        }
    }
    
    return arr
}

• 相关文章
• 全局相关文章