舒适的湿度

难度: Hard

力扣嘉年华为了确保更舒适的游览环境条件，在会场的各处设置了湿度调节装置，这些调节装置受控于总控室中的一台控制器。控制器中已经预设了一些调节指令，整数数组`operate[i]` 表示第 `i` 条指令增加空气湿度的大小。现在你可以将任意数量的指令修改为降低湿度（变化的数值不变），以确保湿度尽可能的适宜： - 控制器会选择 **一段连续的指令** ，从而进行湿度调节的操作； - 这段指令最终对湿度影响的绝对值，即为当前操作的「不适宜度」 - 在控制器所有可能的操作中，**最大** 的「不适宜度」即为「整体不适宜度」请返回在所有修改指令的方案中，可以得到的 **最小** 「整体不适宜度」。 **示例 1：** > 输入：`operate = [5,3,7]` > > 输出：`8` > > 解释：对于方案 `2` 的 `[5,3,-7]` >操作指令 `[5],[3],[-7]` 的「不适宜度」分别为 `5,3,7` >操作指令 `[5,3],[3,-7]` 的「不适宜度」分别为 `8,4` >操作指令 `[5,3,-7]` 的「不适宜度」为 `1`， >因此对于方案 `[5,3,-7]`的「整体不适宜度」为 `8`，其余方案的「整体不适宜度」均不小于 `8`，如下表所示： ![image.png](https://pic.leetcode-cn.com/1663902759-dgDCxn-image.png){:width=650px} **示例 2：** > 输入：`operate = [20,10]` > > 输出：`20` **提示：** - `1 <= operate.length <= 1000` - `1 <= operate[i] <= 1000`

Submission

运行时间: 47 ms

内存: 16.2 MB

class Solution:
    def unSuitability(self, operate: List[int]) -> int:
        def maybe(d: int) -> bool:
            u = mask = (2 << d) - 1
            for x in operate:
                u = ((u << x) | (u >> x)) & mask
            return u > 0

        return bisect_left(range(2 * max(operate) + 1), True, lo=min(operate), key=maybe)

Explain

此题解采用了二分搜索和位操作来解决问题。核心想法是，定义一个函数 `maybe(d)`，用来判断是否存在一种指令修改方式，使得所有连续段的湿度调整绝对值都不超过 `d`。在 `maybe` 函数中，使用了位操作来动态地记录和更新可能的湿度调整值。具体来说，用一个位掩码 `mask` 来表示可能达到的湿度范围，通过左移和右移操作来模拟增加和降低湿度的效果。然后使用二分搜索方法在可能的湿度范围内寻找最小的 `d` 值，使得 `maybe(d)` 返回为 `True`。这样找到的 `d` 就是题目要求的最小「整体不适宜度」。

时间复杂度: O(n * log(max(operate)))

空间复杂度: O(1)

class Solution:
    def unSuitability(self, operate: List[int]) -> int:
        def maybe(d: int) -> bool:
            # 生成最大可能的湿度变化的掩码
            u = mask = (2 << d) - 1
            for x in operate:
                # 更新 u 来反映增加或减少湿度 x 的可能结果
                u = ((u << x) | (u >> x)) & mask
            # 如果 u 中存在非零位，则表示存在一种调整方法使得不适宜度不超过 d
            return u > 0

        # 使用二分搜索找到最小的 d 值，使得 maybe(d) 为 True
        return bisect_left(range(2 * max(operate) + 1), True, lo=min(operate), key=maybe)

Explore

在`maybe`函数中，位掩码`mask`是通过`(2 << d) - 1`来创建的，这意味着它将包括`2^(d+1) - 1`比特位，这些位均初始化为1。掩码的大小确保了可以表示从0到`d`的湿度调整。通过左移或右移操作，掩码表示了增加或减少湿度后的所有可能状态。位操作确保了所有可能的状态都能被考虑到，但可能存在超出初始湿度范围的值由于位数限制而被截断，这可能导致某些调整值的错误表示。例如，如果湿度调整超过了`d`，那么这些超出范围的调整可能会被错误地映射到较小的值。

二分搜索的范围从`min(operate)`到`2 * max(operate) + 1`是基于湿度调整的极端情况进行估计的。`min(operate)`提供了一个理论的最小范围，因为即使最小的操作也应当考虑。由于最大可能的湿度调整是在每次操作都是最大值的情况下发生的，`2 * max(operate)`考虑了这种连续两次操作可能导致的最大变动。加1是为了确保二分搜索的上限是闭区间，使得算法可以正确地处理边界值。这个范围确保了搜索空间足够大，能够覆盖所有可能的不适宜度值。

在`maybe(d)`函数中，位操作是通过左移和右移来模拟湿度的增加和减少。具体地，对于每一个操作值`x`，湿度的增加通过`u << x`表示，即将现有的可能湿度状态集合向左移动`x`位，表示每个可能的状态都增加了`x`单位的湿度。同理，湿度的减少通过`u >> x`表示，即向右移动`x`位。这两个操作的结果通过逻辑或操作`|`合并，表示任一增加或减少`x`单位湿度的可能性。最后，使用`& mask`操作确保结果仅包含在有效的位范围内，即去除因位移操作而超出范围的部分。这样，每次操作后，`u`都会更新为新的可能状态集合，直至遍历完所有操作。