难度: Easy
Submission
运行时间: 28 ms
内存: 16.7 MB
from typing import List
class Solution:
def transformArray(self, arr: List[int]) -> List[int]:
n = len(arr)
while True:
changed = False
new_arr = [arr[0]] # Create a new array with the first element
for i in range(1, n - 1):
if arr[i] < arr[i - 1] and arr[i] < arr[i + 1]:
new_arr.append(arr[i] + 1)
changed = True
elif arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
new_arr.append(arr[i] - 1)
changed = True
else:
new_arr.append(arr[i])
new_arr.append(arr[-1]) # Append the last element to the new array
if not changed:
return new_arr
arr = new_arr # Update the array for the next iteration
# Test the solution
solution = Solution()
print(solution.transformArray([6, 2, 3, 4])) # Output: [6, 3, 3, 4]
print(solution.transformArray([1, 6, 3, 4, 3, 5])) # Output: [1, 4, 4, 4, 4, 5]
Explain
解题思路是采用迭代方法对数组进行变换。在每次迭代中，我们创建一个新数组，从头到尾检查每个元素。如果一个元素比它的前一个和后一个元素都小，则将其加一；如果一个元素比它的前一个和后一个元素都大，则将其减一。如果数组在某次迭代后没有发生任何变化，即没有元素被加一或减一，那么迭代结束，输出最终的数组。
时间复杂度: O(kn)
空间复杂度: O(n)
from typing import List
class Solution:
def transformArray(self, arr: List[int]) -> List[int]:
n = len(arr) # 获取数组长度
while True:
changed = False # 标记数组在本次迭代中是否发生了变化
new_arr = [arr[0]] # 创建新数组并初始化为第一个元素
for i in range(1, n - 1):
if arr[i] < arr[i - 1] and arr[i] < arr[i + 1]:
new_arr.append(arr[i] + 1) # 符合增加条件
changed = True
elif arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
new_arr.append(arr[i] - 1) # 符合减少条件
changed = True
else:
new_arr.append(arr[i]) # 保持当前值
new_arr.append(arr[-1]) # 添加最后一个元素到新数组
if not changed:
return new_arr # 如果没有变化，返回结果
arr = new_arr # 用新数组更新原数组以进行下一次迭代
# Test the solution
solution = Solution()
print(solution.transformArray([6, 2, 3, 4])) # Output: [6, 3, 3, 4]
print(solution.transformArray([1, 6, 3, 4, 3, 5])) # Output: [1, 4, 4, 4, 4, 5]
Explore
该算法定义了迭代停止的条件为一次迭代后数组没有任何变化，即没有元素被增加或减少。这种情况确保了只要数组的状态发生了改变，迭代就会继续。因此，在理论上不会出现过早停止的问题。即使在数组较长或元素变化微小的情况下，只要任意元素需要调整，迭代就会继续。这种停止条件确保了算法只在达到稳定状态时停止，这时所有符合条件的元素已经被调整至不再需要变化。
在该算法中，数组的第一个和最后一个元素（边界元素）被直接添加到新数组中而没有进行任何增加或减少的操作。这种处理方式是基于边界元素只有一个相邻元素的事实，使得它们没有完全的比较基础来判断是否需要增减。这可能不会影响算法的整体效果，因为边界条件通常由问题本身的特性决定。然而，在某些特殊情况下，如果边界元素的处理对结果有重要影响，可能需要对算法进行调整，例如考虑边界元素与其内部相邻元素的关系，以确保更精确的处理。
算法通过在每次迭代中创建一个新数组来处理元素的连续变化。在每次迭代的开始，都基于上一次迭代的结果来判断每个元素是否需要增加或减少。这种方法确保了每次迭代都是基于最新的数组状态进行的，从而避免了在多次迭代中重复无效修改同一元素。此外，由于每次迭代后数组的状态都被重新评估，元素在增加后立即满足减少条件的情况将在下一次迭代中被处理，反之亦然。这保证了算法可以适应元素的连续变化，最终达到一个稳定状态。