LeetCode题目

题目分析 本题首先规定了游戏规则如下： 将当前余下的石头分成左右非空的两部分； 分别计算两部分的石头价值总和，若两者不等，则保留总和较小的一部分，否则任选一部分保留； 将留下的石子价值总和计入$Alice$的得分； 按照上述规则一直进行游戏，直到只剩下一个石子为止。求$Alice$的最大得分。 基本思路 如果进行了一次分割，那么无论最终留下哪一部分，其实问题都变成了一个规模更小但相似的子问题，故可以想到用动态规划进行解决，定义动态规划数组$dp$，其中$dp[i][j]$表示在区间$[i,j)$中$Alice$能够取得的最大得分，那么将$k$在$(i,j)$中遍历，则$dp[i][j]$的计算需要分以下两种情况： 为方便叙述，记$stoneValues[i:k]$的总和为$left$，$stoneValues[k:j]$的总和为$right$。 $$ dp[i][j] = max \begin{cases} dp[i][k]+left &,left\leq right\\ dp[k][j]+right &,left\geq right \end{cases} $$不难发现，由于$stoneValues$中的所有值都是正数，那么随着$k$的增加，$left$必定越来越大，$right$必定越来越小，故一定存在下标$p$，使得当$k\in (i,p]$时均满足$left\leq right$，同理，一定存在下标$q$，使得当$k \in [q,j)$时均满足$left \geq right$，可以发现，当存在一个$k$使得$left=right$时，$q=p$，否则，$q=p+1$。 因此，如果用前缀和数组$s$表示出$left$和$right$，并结合上述分析即可得到： $$ dp[i][j] = max \begin{cases} \max\limits_{k=i+1}^{p}(dp[i][k]+s[k]-s[i])\\ \max\limits_{k=q}^{j-1}(dp[k][j]+s[j]-s[k]) \end{cases} $$将与$k$无关的项提取出来即可得到： $$ dp[i][j] = max \begin{cases} -s[i]+\max\limits_{k=i+1}^{p}(dp[i][k]+s[k])\\ s[j]+\max\limits_{k=q}^{j-1}(dp[k][j]-s[k]) \end{cases} $$可以发现，后面求最大值的项中，$k$都是在区间$[i,j]$的前缀或后缀中遍历的，故如果能维护一个特定区间中指定式子的前缀最大值和后缀最大值，就可以快速求出$dp[i][j]$的值，定义前缀最大值数组$preMax[i][j]$表示$\max\limits_{k=i+1}^{j}(dp[i][k]+s[k])$，同时定义后缀最大值数组$sufMax[i][j]$表示$\max\limits_{k=i}^{j-1}(dp[k][j]-s[k])$，那么上面的递推关系式就变成了： $$ dp[i][j] = max \begin{cases} -s[i]+preMax[i][p]\\ s[j]+sufMax[q][j] \end{cases} $$同时根据定义可以得知$preMax$和$sufMax$数组的递推关系如下： $$ \begin{align} preMax[i][j] = max(preMax[i][j-1], dp[i][j]+s[j])\\ sufMax[i][j] = max(sufMax[i+1][j], dp[i][j]-s[i]) \end{align} $$有了递推关系式，接下来就需要确定区间左右端点遍历的顺序，注意到，在计算$preMax$的值时，位置$(i,j)$是由位置$(i,j-1)$转移过来的，说明$j$的遍历应当从前往后遍历，同时在计算$sufMax$的值时，位置$(i,j)$是由位置$(i+1,j)$转移过来的，说明$i$的遍历应当从后往前遍历。不过需要注意的是，并不是两个数组中的值都需要在$dp[i][j]$计算完毕后才更新，因为在计算$dp[i][j]$时，实际上需要用到一个$preMax[i][p]$，而$p$是在$i$之后的，故应当在向后计算$p$的位置时同步更新$preMax$中的值。 最后在$dp$中所有值计算完毕后，返回$dp[0][n]$即为答案。 实现细节 如果对于每一个区间都用遍历去寻找$p$和$q$的位置，时间复杂度则会到达$O(n^3)$，故需要将其简化，注意到当确定区间左端点$i$之后，由于$j$的遍历顺序是从前往后，因此$p$和$q$的位置一定是不断右移的，故对于每一个固定$i$的循环，都可以初始化一个$p$的位置，随着$j$的增加，每次都用while循环增加$p$直到满足要求，这样，对于每一个不同的$i$，$p$最多也就循环$n$次，而非暴力的$n^2$次，复杂度即可降为$O(n^2)$。 ...

题目分析 本题要求的是将$s$重排形成的所有回文串进行排序，并返回第$k$小的那个回文串。 基本思路 首先，既然题目要求将本就是回文串的$s$重排形成另外的回文串，那么实际上需要重排的只是$s$的左边一半，只要得到左边一半的所有字符组成的所有排列中第$k$小的排列，那么将它倒序后和它进行拼接即可得到答案（注意，如果原字符串长度为奇数，则需要将$s$的中间字符插在两个拼接的排列中间，因为整个字符串中只有这一个字符出现了奇数次，无论如何它都必须放在中间）。 因此，问题就转换成了：取出$s$的左边一半$left$，并求它形成的第$k$小的排列。 但，怎么找出第$k$小的排列呢？注意到，如果将一个字符串重排形成的所有排列放在一个列表中进行从小到大排序，那么排完之后，列表中所有元素的首字母一定从左到右是非递减的，同样的，在首字母相同的一段排列中，第2个字母一定从左到右也是非递减的，以此类推，只要一段排列的前$x$个字符都相同，那么它们的第$x+1$个字符一定从左到右是非递减的。综上所述，如果要找到第$k$小的那个排列，可以考虑在每一个位置按照字母从小到大的顺序依次尝试填入，即可保证得到的排列一定是不断变大的。 不过如果直接这样暴力模拟填写字母直到第$k$个，最坏情况下可能要将所有可能的排列都遍历完，复杂度可能达到$O(26^n)$，一定超时。那么如果能够在每一个位置都可以只循环一遍剩余能填的字母就判断出这个位置该填哪个，时间复杂度最坏情况下也只有$O(26n)$（每个位置都遍历所有字母），就可以通过。 如何实现？对于第一个位置，首先从小到大遍历可以选的所有字母，假如现在在第一个位置填上某一个字母，那么后面能填的各种字母的个数必定发生变化，根据剩余字母的个数，结合组合数学即可求出后面$n-1$个位置所有排列的总情况数，加上之前累计的情况数即可得到在该情况下能够达到最大的排列是第几小，如果还未超过$k$，就直接加到累计情况总数中，继续尝试下一个字母，否则，只要大于等于$k$，就不累加并进入到下一个位置的选择中。 这样，从头开始逐位挑选合适的字符，即可让累计情况数不断向$k$逼近，最终到达$k$，将填出来的字串还原即得答案。当然，如果最终选不出和$left$一样长的字符串，就说明总情况数小于$k$，返回"“即可。 计算组合数方法即代码优化 根据上面所说，程序中需要根据一个字符串中各个字符的个数计算它们能够组成的不同排列总数。假设剩余字符总个数为$m$，且$cnt[x]$表示字符$x$的剩余个数，那么不同的排列总数就是： $$ \frac{m!}{cnt[a]!\times cnt[b]!\times \cdots \times cnt[z]!} $$ 上面是未考虑重复字符情况下的总排列数，下面是针对每个字符的重复次数进行去重。 但如果每次计算时都遍历一次所有字母计算排列总数，大数计算次数太多，太慢了，需要进行优化。注意到，如果位置$i$选择填字母$x$，令$m$为从$i$开始到左半边字符串结尾的长度，那么在修改$cnt$数组数据之前计算出来的排列总数为： $$ \frac{m!}{cnt[a]!\times \cdots \times cnt[x]!\times \cdots \times cnt[z]!} $$ 而在修改后计算出来的排列总数为： $$ \frac{(m-1)!}{cnt[a]!\times \cdots \times (cnt[x]-1)!\times \cdots \times cnt[z]!} $$注意到，后者比前者的分母少了$m$，分子少了$cnt[x]$，因此，如果能够保存下来上一个位置选定字母后剩余位置的排列总数$last$，当前选定字母后剩余位置的排列总数就是： $$ last\times \frac{cnt[x]}{m} $$综上所述，如果最开始能够计算出来总共的排列总数，即可在循环中用滚动计算得到当前情况下剩余位置的排列总数。 复杂度 时间复杂度：$O(nlogn)$ 空间复杂度：$O(n)$ 代码 maxNum = 10001 prod = [1]*maxNum for i in range(1, maxNum): prod[i] = prod[i-1]*i def comb(m, n): return prod[m]//(prod[m-n]*prod[n]) class Solution: def smallestPalindrome(self, s: str, k: int) -> str: n = len(s) left = s[:n//2] cnt = [0]*26 for c in left: cnt[ord(c)-ord('a')] += 1 val = prod[n//2] # 计算所有位置的排列总数 for i in cnt: if i == 0: continue val //= prod[i] left = ''.join(sorted(left)) res = "" counted = 0 # 累计排列总数 for i in range(n//2): for j in range(26): # 从小到大试填 if cnt[j]: # 第j个字符还有剩余 cnt[j] -= 1 # 计算当前前缀下剩余位置的排列总数 cur = val*(cnt[j]+1)//(n//2-i) if counted+cur >= k: # 超过了k，可以填入 val = cur # 准备下次计算 res += chr(ord('a')+j) break counted += cur # 计入累计排列总数 cnt[j] += 1 if len(res) < n//2: return "" res = res+(s[n//2] if n&1 else '')+res[::-1] # 还原成回文串 return res

题目分析 本题要求的是长度为$k$的数组数量，且这些数组需要保证： 数组中数字总和为$n$； 数组中数字乘积为偶数； 注意需将求出的数组数量对$10^9+7$取余后返回答案。 基本思路 DFS+记忆化搜索（超时） 分析题目可以发现，实际上这个数组中只需要保证至少有一个偶数，即可满足题目的第2个要求，因此可以用$DFS$进行填数字，最终判断所填的数字中是否有偶数出现，即可判定填出来的数组是否符合要求，具体$DFS$函数如下： def dfs(pos, left, hasEven): if pos == k-1: return int(hasEven | (left%2==0)) res = 0 for i in range(1, left-(k-pos-1)+1): res = (res+dfs(pos+1, left-i, hasEven|(i%2==0)))%modNum return res 需要注意的是，在从左向右第$pos$位上填数字时，若在保证总和为$n$的前提下剩下数字的总和为$left$，那么为保证后面的位置还可以至少填1，当前所能填的最大数字只能是$left-(k-pos-1)$。 不过可惜的是，如此简洁优雅的代码只能通过369/803个测试用例，因此只能更换算法。 组合数计算 前置知识 现有一个问题如下： 已知一个列表长度为$a$，总和是$b$($a\leq b$)，且其中所有元素均为正整数，那么共有多少个该种列表？ 为解决这个问题，可以这样考虑，如果有$b$个小球顺次排开，在所有缝隙之中插入$a-1$个挡板，只要保证没有两个挡板插在同一个缝隙，且没有挡板插在最左或最右边，那么即可将这$b$个小球分成$a$堆，同时满足每堆数量均为正整数。这样，将每一堆小球的数量组成一个列表，这就是一个符合要求的列表。 而$b$个小球中总共有$b-1$个空隙，现在又要插$a-1$个挡板，那么总共合规的情况数，即满足要求的列表数量即为：$C_{b-1}^{a-1}$. 可以发现，利用组合数其实可以很简单计算出来总情况数量，即$C_{n-1}^{k-1}$，那么如果能用同样的方式计算出来无效序列数目，两个相减即可得到有效序列数目了。 什么是无效序列数目呢？题目要求数组中所有数字的乘积是偶数时才表明该数组是有效序列，那么无效序列就是所有数字乘积为奇数的数组，这么看来，只有全部都是奇数的数组才是无效序列。下面来求全部都是奇数，且总和为$n$，长度为$k$的数组数量。 每一个奇数都可以表示为$2x_i - 1(x_i\geq 1)$，因此要求的实际上就是数列$[x_0, x_1, \dots, x_{k-1}]$的数量，且数列满足： $$ \sum_{i=0}^{k-1} (2x_i-1) = n $$将求和式子展开后可得： $$ 2\sum_{i=0}^{k-1} x_i - k = n $$化简可得： $$ \sum_{i=0}^{k-1} x_i = \frac{n+k}{2} $$因此，问题就转换成了：求长度为$k$，总和为$\frac{n+k}{2}$且均为正整数的数列数量，和「前置知识」中的问题相同，注意到如果$n+k$是奇数，不可能有符合要求的任何数列，故可知，无效序列的总数为： $$ \begin{cases} C_{\frac{n+k}{2}-1}^{k-1} &, n+k为偶数\\ 0 &, n+k为奇数 \end{cases} $$综上所述，即可得知有效序列的总数为： ...

题目分析 本题要求在给定的数组$nums$中找到最大的回文子数组的总和。 基本思路 找回文子数组，首先要确定这个子数组的中间点，由于题目数据保证了$1 \leq nums[i] \leq 10^9$，即$nums$中所有数字都是正数，因此如果确定了一个回文子数组的中间点，为了让总和最大化， 就要让回文子数组的长度尽可能大，故问题转换成了：对于每一个位置，求出以它为中间点的回文子数组的最大长度，剩下的求和即可用前缀和直接求解。 根据这个问题，可以想到用$Manacher$算法进行求解。下面详细介绍该算法。 Manacher算法详解 正常来说，如果要用中心扩展法(即选定一个中间点，然后暴力模拟向左右两边扩展回文子数组)来检索数组中的回文子数组，不仅效率低下，同时还要根据子数组长度的奇偶性不同分两种情况考虑，比较复杂。为了解决分情况复杂的问题，$Manacher$算法提出了一个新思路：在原数组每相邻两个数字之间插入相同的分隔数字，然后只寻找长度为奇数的回文串，即可囊括原先的所有情况。 这是为什么呢？如果原数组中有一个回文串，长度是奇数，那么这个回文串中的间隔数量就是偶数，故在这个回文串中的每相邻两个数字之间都插入分隔数字后，整个数组的长度就变成了奇数；同理，如果原回文串长度是偶数，那么间隔数量就是奇数，故插入之后数组长度同样变成了奇数。综上所述，只需在新数组中寻找所有可能的奇数长度的回文串即可。这就简化了原问题。 之后就是优化计算的部分。当使用中心扩展法计算以位置$i$为中心位置的最大回文子数组长度时，如果之前在计算某一个位置的时候已经将子数组右端点扩展超过位置$i$，那么重新开始扩展的前半部分进程其实是和之前重复的，这就可以用以下方法进行简化。 定义数组$P$，其中$P[i]$表示以$i$为中点的回文子数组的最大半径。假设现在要计算$P[i]$，且已经计算出$P[:i]$中的所有值，在已知信息中，曾扩展到达的最右侧位置记为$maxRight$，其对应的子数组中点记为$maxCenter$，那么对$P[i]$的计算就可以分以下两种情况： $i> maxRight$，这时没有任何之前的信息可以利用，只能从它开始用中心扩展法计算； $i \leq maxRight$，这时$i$在以$maxCenter$为中点的最大回文子数组内，也就意味着区间$[2\times i-maxCenter, maxCenter]$在之前已经被遍历过，可以利用之前的信息： 求出$i$关于$maxCenter$的对称点$j$，即得到$j=2\times maxCenter-i$，由于两者都在回文子数组内，所以$i$周围的数字情况一定范围内和$j$周围的数字情况是相同的，因此$P[i]$的值可能是$P[j]$； 由于无法保证在位置$maxCenter$右侧的所有数据都和$2\times maxCenter-maxRight$左侧的数据相同，因此$P[i]$的值应当先和$maxRight-i+1$取一个最小值，防止错算； 从已经确定的$P[i]$最小值开始继续用中心扩展法，寻找更大的可能值。 情况2.2可以借助以下图例进行理解： ①. $i+P[j] \leq maxRight$： ②. $i+P[j]>maxRight$： 综上所述，$P[i]$可以根据情况首先确定初始值，然后再用中心扩展法继续计算，这样就可以优化掉最初循环的那一部分。 实现细节 在本题中，由于数据保证所有数字都大于等于1，且最终要求和，所以分隔数字可以采用0. 在最终计算答案时，对于每一个位置$i$求出其对应的$P[i]$后，即可得到以$i$为中点的最大回文子数组的做右端点，用前缀和进行计算并求最大值即可。 注意在循环过程中需要不断维护已知最大右端点和其对应的子数组中点位置。 复杂度 时间复杂度：$O(n)$ 空间复杂度：$O(n)$ 代码 class Solution: def getSum(self, nums: List[int]) -> int: newNums = [0] for i in nums: newNums.append(i) newNums.append(0) n = len(newNums) preSum = [0]*(n+1) for i in range(n): preSum[i+1] = preSum[i]+newNums[i] res = 0 P = [0]*n P[0] = 1 mxCenter, mxRight = 0, 0 for i in range(1, n): if i <= mxRight: j = 2*mxCenter-i P[i] = min(P[j], mxRight-i+1) l, r = i-P[i], i+P[i] while l>=0 and r<n and newNums[l] == newNums[r]: l -= 1 r += 1 P[i] += 1 res = max(res, (preSum[r]-preSum[l+1])) if r-1 > mxRight: mxRight = r-1 mxCenter = i return res

题目分析 本题需要首先在数组$nums$中选择一个子数组，并对其中所有元素都乘以或除以$k$，之后在整个数组中选出一个最大的子数组总和。 基本思路 贪心(无法通过) 如果要完全按照题目的顺序进行模拟计算，太过复杂，并且选择所有可能的子数组分别计算的时间复杂度太高，因此正难则反，既然要操作以后求最大的子数组总和，那为什么不能先求出原先$nums$中的最大子数组总和，然后再通过乘除$k$得到最后的答案呢？ 理论上这是可以的，如果已知原先$nums$中的最大子数组总和为$maxSum$，那么答案就有两种情况： 当$maxSum>0$时，为了让最终的答案尽可能的大，就需要将其乘以$k$，即答案为$maxSum\times k$； 当$maxSum<0$时，为了让答案尽可能大，则需要将其除以$k$，即答案为$\lceil \frac{maxSum}{k} \rceil$； 因此根据上面的分析可以简单写出以下贪心代码： class Solution: def maxSubarraySum(self, nums: List[int], k: int) -> int: sum_num = nums[0] max_sum_num = nums[0] for i in nums[1:]: if sum_num < 0: sum_num = 0 sum_num += i max_sum_num = max(sum_num,max_sum_num) if max_sum_num > 0: max_sum_num *= k else: max_sum_num = -(abs(max_sum_num)//k) return max_sum_num 可惜的是，在提交之后，上面代码并不能通过全部测试用例，而是卡在了$717/718$的位置上，一直到竞赛结束后才发现那个测试用例长这样： $$ \begin{align} &nums = \underbrace{[-8,5,-8,10,-8,5,-8,10,\dots,-8,5,-8,10]}_{总共100个-8,5,-8,10循环}\\ &k = 5 \end{align} $$按照上面的贪心算法，首先在$nums$中求出最大子数组和，可以得到$maxSum=10$，之后根据判断条件，即可得到最终的答案是$maxSum\times k=50$，但这并不是正确答案，原因在于如果在原数组中先找最大子数组和，寻找过程中会发现单独一个循环节的和是： $$ -8+5-8+10=-1 $$ 但如果将所有数字都按照题目要求的方式整除$k=5$后，上面的四个数字就会变成： $$ \begin{align} -8&\rightarrow -1\\ 5&\rightarrow 1\\ 10&\rightarrow 2\\ \end{align} $$ 于是四个数字相加就变成了： ...

题目分析 本题实际上要求的是满足以下条件的数组数量： 长度为给定值$n$； 每一个值都在限定范围$[l,r]$内； 相邻两个位置的关系从左到右依次增减交替变化。 基本思路 动态规划思路 由于本题要保证的只是数字的大小关系，并没有强制要求按照区间$[l,r]$进行计算，因此为了简便计算，可以将$l$和$r$都减少$l$，使区间变为$[0,r-l]$，这和原有情况是等价的。 本题要求最终的数组长度为$n$，如果此时确定第$n$个数字是$x$，并且确定最后两个数字呈上升趋势，那么就可以确定第$n-1$个数字的取值范围，这样，问题其实变成了一个相似但规模更小的问题。因此可以使用动态规划来解决该问题。仿照上面的分析，可以定义两个动态规划数组如下： $dp0[i][j]$表示数组长度为$i$且第$i$个数字为$j$时，最后两个数字呈上升趋势的情况下，数组的总数量； $dp1[i][j]$表示数组长度为$i$且第$i$个数字为$j$时，最后两个数字呈下降趋势的情况下，数组的总数量。 这样，答案就应该是$sum(dp0[n])+sum(dp1[n])$。 那么对于$dp0[i][j]$，由于最后两个数字呈上升趋势，因此可以确定第$i-1$个数字的取值范围为$[l,j-1]$，并且第$i-2$和第$i-1$个数字必须呈下降趋势，故可得递推公式如下： $$ dp0[i][j] = \sum_{k=l}^{j-1}dp1[i-1][k] $$类似的，对于$dp1[i][j]$，也可以得到递推公式如下： $$ dp1[i][j] = \sum_{k=j+1}^{r}dp0[i-1][k] $$根据上面两个公式，即可写出动态规划代码。观察到在递推关系式中用到了区间求和，因此可以用前缀和来优化，当加上前缀和优化时，本题目的第$I$题即可通过了。 矩阵乘法和快速幂优化 观察上面两个递推式子，不难发现，如果将$dp0[i]$和$dp1[i]$合并成一个长度为$2 \times (r-l+1)$的数组$dp[i]$，那么每一个$dp[i]$实际上都可以用同样一个公式从$dp[i-1]$中计算得来，而如果将$dp[i]$看作一个维度是$2 \times (r-l+1)$的空间中的一个坐标，那么上面说的这个递推公式其实可以看作一个坐标变换矩阵，每次只需用同样的矩阵乘以原来的坐标，即可得到新的坐标。 （注意，两个数组经过上述合并后，$dp0$中原有的索引不变，但$dp1$中原有的索引会增加$r-l+1$。为叙述方便，定义$k = r-l+1$） 举个例子，如果$k=2$，也就意味着数组中的每个位置上都只有两个数字可以选，那么根据之前的递推公式可以得到： $dp0[i][0] = 0$; $dp0[i][1]=dp1[i-1][0]$; $dp1[i][0]=dp0[i-1][1]$; $dp1[i][1] = 0$. 而如果将$dp0[i][x]$换成$dp[i][x]$，并将$dp1[i][x]$换成$dp[i][x+k]$，即可得到以下递推式： $dp[i][0] = 0$; $dp[i][1] = dp[i-1][2]$; $dp[i][2] = dp[i-1][1]$; $dp[i][3] = 0$; 因此可以整理出从$dp[i-1]$转成$dp[i]$所需要进行的坐标变换矩阵如下： $$ \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix} $$总结规律，可以发现，对于任意一个$k$值，对应的坐标变换矩阵都可以按照下面方式列写： ...

题目分析 本题要求的是至多选$m$次元素时能够得到的最大总价值，且对于第$i$个元素，每选择它一次，它的价值就会减少$decay[i]$，即从$value[i]$变成$value[i]-decay[i]$。 基本思路 大顶堆模拟 最直接的思路就是模拟选取元素，如果对于每一个位置都将其对应的二元组$(value[i], decay[i])$存入一个大顶堆中，那么在一次选取元素的过程中，直接取出堆顶元素即可最大化当前选取的价值。假设当前弹出的堆顶元素是$(v_i, d_i)$，那么根据题目要求，「选择元素$i$后其价值会减少$decay[i]$」，则需要将更新价值后的该元素,即二元组$(v_i-d_i, d_i)$再次压入堆中。 虽然这是一个暴力模拟方法，但依然可以加入一点优化，即在模拟$m$次选取的$while$循环中，如果某次选择元素时，整个堆中的最大值都小于0了，即可直接退出循环，因为这时再加下去也没有意义了，只会让总和变得更小。 根据上述思路，即可简单写出暴力模拟的代码如下： class Solution: def maxTotalValue(self, value: list[int], decay: list[int], m: int) -> int: n = len(value) hp = [] for i in range(n): heappush(hp, (-value[i], decay[i])) res = 0 modNum = 1_000_000_007 while m: m -= 1 cur, d = heappop(hp) cur = -cur if cur < 0: break res = (res+cur)%modNum heappush(hp, (-(cur-d), d)) return res 确实很简单，但实测只能通过221 / 561个测试用例，因此需要整个优化。 二分查找优化 如果说在整个数组中选至多$m$个元素比较困难，那么可以倒过来想，由于每一个值在选择的过程中它会变得越来越小，因此如果确定了一个最小值的界限，实际上就可以确定一个元素能够被选择的次数。具体操作是这样的： 已知要选的所有值都要大于阈值$X$，且对于元素$i$，它初始值是$v_i$，每选择它一次值就会减少$d_i$； 那么能够减少$d_i$的次数就是：$cnt=\lfloor \frac{v_i-X-1}{d_i} \rfloor$；（其中-1是为了保证减少后其值大于$X$） 因此该元素能够被选择的次数就是：$cnt+1$. 综上所述，如果$X$增大，那么总共选择的数量就一定非增(不变或减小)，否则总共选择的数量就一定非减(不变或增大)，即总共选择的数量随$X$的增大呈有序分布状态，因此可以考虑用二分查找的方式寻找一个能够满足总共选择数量小于等于$m$的最小阈值$X$。 ...

题目 在一座城市里，你需要建 n 栋新的建筑。这些新的建筑会从 1 到 n 编号排成一列。 这座城市对这些新建筑有一些规定： 每栋建筑的高度必须是一个非负整数。 第一栋建筑的高度 必须 是 0 。 任意两栋相邻建筑的高度差 不能超过 1 。 除此以外，某些建筑还有额外的最高高度限制。这些限制会以二维整数数组 restrictions 的形式给出，其中 restrictions[i] = [idi, maxHeighti] ，表示建筑 idi 的高度 不能超过 maxHeighti 。 题目保证每栋建筑在 restrictions 中 至多出现一次 ，同时建筑 1 不会 出现在 restrictions 中。 请你返回 最高 建筑能达到的 最高高度 。 思路 每一个限制都有可能影响到所有建筑物的最高高度，因此可以这样考虑： 先向右遍历一遍所有的限制，根据左侧一个限制位置的最高高度即可计算出当前限制位置的最高高度。即，如果位置i左侧最近一个限制的位置是j，且已知j的最高高度为h，那么位置i的最高高度就应该是$h+(i-j)$； 再向左遍历一遍所有的限制，按照同样的方法处理一遍所有的限制位置对应的最高高度，即可得到在所有限制下，每个位置可以达到的最高高度。 得到了每个限制位置可以达到的最高高度后，就需要计算答案了，需要注意的是，答案不仅仅是每个限制位置上的最高高度的最大值，而是每一个位置上可能的最高高度的最大值，因此需在两个已知最大高度的相邻限制位置之间求一个可能的最大高度。 如果两个相邻限制位置i和j对应的最大高度分别为$h_i$和$h_j$，那么假设在它中间的位置上有一个最大的高度best，由于题目限制了任意两栋相邻的建筑高度差最大为1，因此best必须满足以下式子： $$ (best-h_i)+(best-h_j) = j-i $$即可求出best最大为: $$ \frac{j-i+h_i+h_j}{2} $$之后，对于每两个相邻的限制位置都求一个中间的最高高度best的最大值，即可得到答案。 代码 class Solution: def maxBuilding(self, n: int, R: List[List[int]]) -> int: R.sort() R.insert(0, [1,0]) # 为了求所有的最高高度，需要在左右都加上哨兵 if R[-1][0] != n: R.append([n, n-1]) m = len(R) for i in range(1, m): R[i][1] = min(R[i][1], R[i-1][1]+(R[i][0]-R[i-1][0])) for i in range(m-2, 0, -1): R[i][1] = min(R[i][1], R[i+1][1]+(R[i+1][0]-R[i][0])) res = 0 for i in range(m-1): best = (R[i+1][0]-R[i][0]+R[i][1]+R[i+1][1])//2 res = max(res, best) return res

题目分析 如果称一个长度$length$「满足条件」，即表示在$nums$中所有长度为$length$的子数组中存在一个唯一的子数组，那么本题要求的，就是最小的满足条件的长度$length$。 基本思路 分析题目可以发现以下两条性质： 如果一个给定的长度$length$无法满足条件，即该长度对应的所有子数组中没有单独出现的，那么所有小于等于它的长度都一定不满足条件，说明要找的最小长度一定是大于$length$的； 相反，如果一个长度$length$可以满足条件，即存在一个单独出现的长度为$length$的子数组，那么在该长度之下可能还有能够满足条件的长度，结合本题要求最小长度，因此要找的长度一定是小于等于$length$的。 可以发现，只要确定一个长度是否满足条件，即可确定需要的答案究竟大于还是小于这个长度，因此可以想到采用二分查找的方式寻找答案。 思路1：列表模拟计算 根据上述分析可以发现，二分查找的判断函数应判断给出的中间值$mid$是否是一个满足条件的长度，因此最暴力的方式就是：直接用列表模拟找所有长度为$mid$的子数组，并逐个转为tuple类型用哈希表计数（转为tuple是因为list类型无法直接在哈希表里当作键来计数），其中列表维护长度为$mid$的子数组，即可采用滑动窗口的方式维护。代码很简单直观，如下： def check(mid): cur = [] tot = defaultdict(int) for i in range(n): cur.append(nums[i]) if i < mid-1: continue tp = tuple(cur) tot[tp] += 1 cur.pop(0) return 1 in tot.values() 不过上面代码中，list转tuple以及pop操作的空间复杂度都很高，最坏情况下单单$tot$中存储值的数量都会逼近$O(n^2)$，因此最终上述代码超内存。 思路2：列表哈希化处理 既然用列表计数会超内存，那么就需要想将列表压缩的方法。可以发现，如果将列表压缩成一个数字，那么空间复杂度将大大降低，因此这里可以借鉴哈希化的方法。 什么叫哈希化？如果要将一个列表哈希化，即意味着用一个特定数字表示该列表。如果要用一个数字$w$代替一个长度为$length$的列表$lst$，则可以使用一个质数$base$，令： $$w = lst[0]\times base^{length-1}+lst[1]\times base^{length-2}+...+lst[length-1]\times base^0$$ 即可使用数字$w$表示列表$lst$。 因此可以定义$w$，表示当前长度为$length$的子数组对应的数字，如果依旧用上述滑动窗口的方式对其增减元素，假设当前要增加的元素是$nums[i]$，那么要删除的元素就是$nums[i-length]$，即可知道$w$的变化如下： $w \rightarrow w\times base$（将每一个元素中$base$的指数都增加1，为新元素腾出位置） $w \rightarrow w-nums[i-length]\times b^{length}$（删除$nums[i-length]$，这里由于上一步将$base$的指数加了1，此处对应的指数就变成了$length$而非原先的$length-1$） $w \rightarrow w+nums[i]$（加上$nums[i]$，此处省略$base^0$） 因此根据上述步骤即可实现元素的增减，从而将所有子数组压缩成一个单独的数字。 实现细节 需要注意的是，如果按照上述的计算方式，当$nums$中的值很大并且$length$很大时，$w$的值就会很大，因此可以使用另一个大质数$mod$来对$w$的值不断取模，从而保证不会超出整数范围，同时减少大数相乘的计算量，减少时间。 同时，按照思路2进行计算时，可以先计算出第一个窗口对应的值，这样，在后面进行增减运算的循环中不会在同一个循环中实现太多功能，增强可读性。 在本题中，如果只用一组$base, mod$数对将每一个子数组进行压缩，不会出现哈希值的冲突，但当数据量增大时，为了防止哈希值的冲突，可以再增加一组$base2,mod2$的值对每一个子数组计算出另一个压缩后的数字，两者同时对应一个子数组，即可降低哈希值冲突的可能性。 （在下面的代码中，我给出了用两组值分别压缩子数组的方式，如果追求运行速度，可以将有关$b2,m2,pow2,w2$的计算全部删除，可以降低运行时间） 复杂度 时间复杂度：$O(n\cdot logn)$ 空间复杂度：$O(n)$ 代码 class Solution: def smallestUniqueSubarray(self, nums: List[int]) -> int: n = len(nums) b1, m1 = 1_000_07, 1_000_000_007 # 第一组数据 b2, m2 = 1_000_09, 1_000_000_009 # 第二组数据 def check(mid): pow1 = pow(b1, mid, m1) pow2 = pow(b2, mid, m2) w1, w2 = 0, 0 for i in range(mid): w1 = (w1*b1+nums[i])%m1 w2 = (w2*b2+nums[i])%m2 # 用第二组数据进行压缩 cnt = defaultdict(int) cnt[(w1, w2)] = 1 for i in range(mid, n): w1 = (w1*b1+nums[i]-nums[i-mid]*pow1)%m1 w2 = (w2*b2+nums[i]-nums[i-mid]*pow2)%m2 # 用第二组数据进行压缩 cnt[(w1, w2)] += 1 for v in cnt.values(): if v == 1: return True return False l, r = 1, n while l<=r: mid = (l+r)//2 if check(mid): r = mid-1 else: l = mid+1 return l