减小和重新排列数组后的最大元素 图解题解

这道题到底在问什么

输入

arr=[2,2,1,2,1]

输出

2

输入

arr=[100,1,1000]

输出

3

输入

arr=[3,9,2,7,3,2]

输出

5

最优解：一步一步想明白

1. 3记牢一句:排序后首位设 1,之后每一位都取 min(原值, 前一个 + 1),最后一位就是答案。下面每帧都在套这句。
2. 4先看清画面。上面是原始数组 [3,9,2,7,3,2],顺序是乱的。右边这块滚动状态记着我们最关心的三样东西,已经定好的下标范围、本步的上限、以及已定的末位值。现在什么都还没处理。要让最后的最大值尽量大,第一步是把数排好序,好让小的数去垫底、大的数往后排。
3. 5把数组从小到大排成 [2,2,3,3,7,9]。为什么要排序?因为首元素必须是 1,而相邻差最多是 1,所以越靠前的位置能取的值越小、越靠后才有机会取到大值。把小的数放前面垫台阶,大的数放后面,才能让末位爬到最高。排好序之后,准备从最左边这一位开始处理。
4. 6处理之前把这一路要用的规则钉牢。最左这一位无论原来是几,都要减成 1,因为题目死规定首元素是 1。从第二位起,每一位有一个天花板,它最多只能比前一个大 1,也就是上限等于前一个的值加 1。可我们只能把数改小、不能改大,万一原值本来就比这个上限还小,那它也升不上去。所以每一位最终落在「原值」和「上限」里较小的那个,一句话就是 min(原值, 前一个 + 1)。下面一位一位地量。
5. 7轮到最左边第一位,排序后它的原值是 2。这一位是特殊位,不用比上限,题目直接规定了首元素得是 1。因为我们能把数改小,把 2 减成 1 完全合法。下一帧就把它落定成 1。
6. 8把第一位正式定成 1,标绿。现在已定的末位值是 1,这就是后面所有位置往上爬的起跑线。记住这条起跑线,第二位的上限就等于它加 1。接着一位一位往右推。
7. 9轮到第 2 位,排序后它的原值是 2。左边蓝色的 1 位已经定好了,其中前一位落定在 1。先把这一位的原值 2 拎出来,下一帧算它的上限,再决定它最终能留到多大。
8. 10这一位的上限是前一位的值加 1,也就是 1 加 1 等于 2。它最多只能到 2,不能更高。现在原值 2 正好卡在上限 2 上,不多不少,直接留着就合法。
9. 11结算:取原值 2 和上限 2 里较小的那个,min(2, 2) 等于 2,把这一位标绿定下来。原值刚好等于上限,原封不动留 2。已定末位值刷新为 2,下一位的上限就是它加 1。
10. 12轮到第 3 位,排序后它的原值是 3。左边蓝色的 2 位已经定好了,其中前一位落定在 2。先把这一位的原值 3 拎出来,下一帧算它的上限,再决定它最终能留到多大。
11. 13这一位的上限是前一位的值加 1,也就是 2 加 1 等于 3。它最多只能到 3,不能更高。现在原值 3 正好卡在上限 3 上,不多不少,直接留着就合法。
12. 14结算:取原值 3 和上限 3 里较小的那个,min(3, 3) 等于 3,把这一位标绿定下来。原值刚好等于上限,原封不动留 3。已定末位值刷新为 3,下一位的上限就是它加 1。
13. 15轮到第 4 位,排序后它的原值是 3。左边蓝色的 3 位已经定好了,其中前一位落定在 3。先把这一位的原值 3 拎出来,下一帧算它的上限,再决定它最终能留到多大。
14. 16这一位的上限是前一位的值加 1,也就是 3 加 1 等于 4。它最多只能到 4,不能更高。现在原值 3 比上限 4 还小。可我们只能减不能加,升不到 4 那么高,只能保留原值 3。这里就是重复值升不上去的情形。
15. 17结算:取原值 3 和上限 4 里较小的那个,min(3, 4) 等于 3,把这一位标绿定下来。原值本来就小于上限,减不了也加不了,就留原值 3。已定末位值刷新为 3,下一位的上限就是它加 1。
16. 18轮到第 5 位,排序后它的原值是 7。左边蓝色的 4 位已经定好了,其中前一位落定在 3。先把这一位的原值 7 拎出来,下一帧算它的上限,再决定它最终能留到多大。
17. 19这一位的上限是前一位的值加 1,也就是 3 加 1 等于 4。它最多只能到 4,不能更高。现在原值 7 比上限 4 还大,超标了。我们能把它改小,所以要把它压到上限 4。
18. 20结算:取原值 7 和上限 4 里较小的那个,min(7, 4) 等于 4,把这一位标绿定下来。原值超了,被上限压到 4。已定末位值刷新为 4,下一位的上限就是它加 1。
19. 21轮到第 6 位,排序后它的原值是 9。左边蓝色的 5 位已经定好了,其中前一位落定在 4。先把这一位的原值 9 拎出来,下一帧算它的上限,再决定它最终能留到多大。
20. 22这一位的上限是前一位的值加 1,也就是 4 加 1 等于 5。它最多只能到 5,不能更高。现在原值 9 比上限 5 还大,超标了。我们能把它改小,所以要把它压到上限 5。
21. 23结算:取原值 9 和上限 5 里较小的那个,min(9, 5) 等于 5,把这一位标绿定下来。原值超了,被上限压到 5。这是最后一位,它的值 5 就是全数组的最大值。
22. 24把最终数组 [1,2,3,3,4,5] 检查一遍。首位是 1,合规;相邻两两相减,1 到 2 差 1,2 到 3 差 1,3 到 3 差 0,3 到 4 差 1,4 到 5 差 1,全都不超过 1,完全合法。整条数组里最大的数就是末位的 5。注意中间有两个 3 挨在一起,那正是原来重复的值升不上去、只能持平的地方。
23. 25回看整条路:排好序 [2,2,3,3,7,9],首位强制减成 1,之后每一位都取 min(原值, 前一个 + 1),末位值一路被推成 2、3、3、4、5。窍门就一句,排序后首位设 1,其余逐位取 min(原值, 前一个 + 1),末位就是答案。最终答案 5。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:
        arr.sort()
        arr[0] = 1
        for i in range(1, len(arr)):
            arr[i] = min(arr[i], arr[i - 1] + 1)
        return arr[-1]

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int n = arr.size();
        arr[0] = 1;
        for (int i = 1; i < n; ++i) {
            arr[i] = min(arr[i], arr[i - 1] + 1);
        }

        return arr[n - 1];
    }
};

import java.util.*;
class Solution {
    public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
        int n = arr.length;
        Arrays.sort(arr);
        arr[0] = 1;
        int ans = 1;
        for (int i = 1; i < n; ++i) {
            arr[i] = Math.min(arr[i], arr[i - 1] + 1);
        }
        return arr[n - 1];
    }
}

复杂度

面试官可能追问