LeetCode 解題筆記：1846. Maximum Element After Decreasing and Rearranging

作者：王一哲
日期：2026年6月28日


LeetCode 題目連結：1846. Maximum Element After Decreasing and Rearranging

解題想法

中等難度題。題目給定陣列 $arr$，假設長度為 $n$，要求在操作之後使相鄰兩項的差絕對小於等於 1，回傳操作後最大的數字。可用的操作有兩種：

1. $arr[i]$ 減 1
2. 將其中兩項 $arr[i], arr[j]$ 交換

我的寫法分為以下 3 步：

1. $arr$ 由小到大排序，將 $arr[0]$ 改成 $1$。
2. 用一層 for 迴圈檢查 $arr[1]$ 到 $arr[n-1]$，如果 $arr[i] - arr[i-1] > 1$，將 $arr[i]$ 改成 $arr[i-1] + 1$。
3. 操作後的最大值一定在 $arr[n-1]$

Python 程式碼

Runtime: 23 ms, beats 76.60%. Memory: 28.30 MB, beats 36.17%.

class Solution:
    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:
        arr.sort()  # 排序
        n = len(arr)  # 數量
        arr[0] = 1  # 首項改成 1
        for i in range(1, n):  # 檢查 arr[1] ~ arr[n-1]
            if arr[i] - arr[i-1] > 1:  # 如果相差大於 1
                arr[i] = arr[i-1] + 1  # 更新 arr[i]
        return arr[-1]  # 最大值在末項

C++ 程式碼

Runtime: 8 ms, beats 63.84%. Memory: 55.16 MB, beats 69.21%.

class Solution {
public:
    int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {
        sort(arr.begin(), arr.end());  // 排序
        int n = (int)arr.size();  // 數量
        arr[0] = 1;  // 首項改成 1
        for(int i = 1; i < n; i++) {  // 檢查 arr[1] ~ arr[n-1]
            if (arr[i] - arr[i-1] > 1) {  // 如果相差大於 1
                arr[i] = arr[i-1] + 1;  // 更新 arr[i]
            }
        }
        return arr[n-1];  // 最大值在末項
    }
};