Posts

1840.最高建筑高度

题目

在一座城市里，你需要建 n 栋新的建筑。这些新的建筑会从 1 到 n 编号排成一列。

这座城市对这些新建筑有一些规定：

  • 每栋建筑的高度必须是一个非负整数。
  • 第一栋建筑的高度 必须 是 0 。
  • 任意两栋相邻建筑的高度差 不能超过  1 。

除此以外，某些建筑还有额外的最高高度限制。这些限制会以二维整数数组 restrictions 的形式给出，其中 restrictions[i] = [idi, maxHeighti] ，表示建筑 idi 的高度 不能超过 maxHeighti 。

题目保证每栋建筑在 restrictions 中 至多出现一次 ，同时建筑 1 不会 出现在 restrictions 中。

请你返回 最高 建筑能达到的 最高高度 。

思路

每一个限制都有可能影响到所有建筑物的最高高度，因此可以这样考虑：

  1. 先向右遍历一遍所有的限制，根据左侧一个限制位置的最高高度即可计算出当前限制位置的最高高度。即，如果位置i左侧最近一个限制的位置是j，且已知j的最高高度为h，那么位置i的最高高度就应该是$h+(i-j)$；
  2. 再向左遍历一遍所有的限制，按照同样的方法处理一遍所有的限制位置对应的最高高度，即可得到在所有限制下，每个位置可以达到的最高高度。

得到了每个限制位置可以达到的最高高度后，就需要计算答案了，需要注意的是，答案不仅仅是每个限制位置上的最高高度的最大值，而是每一个位置上可能的最高高度的最大值，因此需在两个已知最大高度的相邻限制位置之间求一个可能的最大高度。

如果两个相邻限制位置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
read more
Posts

3934. 最短唯一子数组

题目分析

如果称一个长度$length$「满足条件」，即表示在$nums$中所有长度为$length$的子数组中存在一个唯一的子数组，那么本题要求的，就是最小的满足条件的长度$length$。

基本思路

分析题目可以发现以下两条性质：

  1. 如果一个给定的长度$length$无法满足条件，即该长度对应的所有子数组中没有单独出现的，那么所有小于等于它的长度都一定不满足条件，说明要找的最小长度一定是大于$length$的；
  2. 相反，如果一个长度$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$的变化如下：

  1. $w \rightarrow w\times base$（将每一个元素中$base$的指数都增加1，为新元素腾出位置）
  2. $w \rightarrow w-nums[i-length]\times b^{length}$（删除$nums[i-length]$，这里由于上一步将$base$的指数加了1，此处对应的指数就变成了$length$而非原先的$length-1$）
  3. $w \rightarrow w+nums[i]$（加上$nums[i]$，此处省略$base^0$）

因此根据上述步骤即可实现元素的增减，从而将所有子数组压缩成一个单独的数字。

实现细节

需要注意的是，如果按照上述的计算方式，当$nums$中的值很大并且$length$很大时，$w$的值就会很大，因此可以使用另一个大质数$mod$来对$w$的值不断取模，从而保证不会超出整数范围，同时减少大数相乘的计算量，减少时间。

同时，按照思路2进行计算时，可以先计算出第一个窗口对应的值，这样，在后面进行增减运算的循环中不会在同一个循环中实现太多功能，增强可读性。

在本题中，如果只用一组$base, mod$数对将每一个子数组进行压缩，不会出现哈希值的冲突，但当数据量增大时，为了防止哈希值的冲突，可以再增加一组$base2,mod2$的值对每一个子数组计算出另一个压缩后的数字，两者同时对应一个子数组，即可降低哈希值冲突的可能性。 （在下面的代码中，我给出了用两组值分别压缩子数组的方式，如果追求运行速度，可以将有关$b2,m2,pow2,w2$的计算全部删除，可以降低运行时间）

read more