leetcode
leetcode 3001 ~ 3050
舒适的湿度

舒适的湿度

难度:

标签:

题目描述

English description is not available for the problem. Please switch to Chinese.

代码结果

运行时间: 47 ms, 内存: 16.2 MB


// 思路:Java Stream API 对于这种需要连续子数组和的问题并不直接支持,我们仍然需要先计算出所有的连续子数组和,然后取其最大和最小值来判断。
import java.util.stream.IntStream;

public class Solution {
    public int minUnfitness(int[] operate) {
        int[] maxSum = {Integer.MIN_VALUE};
        int[] minSum = {Integer.MAX_VALUE};
        int[] currentMax = {0};
        int[] currentMin = {0};
        IntStream.of(operate).forEach(num -> {
            currentMax[0] = Math.max(num, currentMax[0] + num);
            maxSum[0] = Math.max(maxSum[0], currentMax[0]);
            currentMin[0] = Math.min(num, currentMin[0] + num);
            minSum[0] = Math.min(minSum[0], currentMin[0]);
        });
        return Math.max(Math.abs(maxSum[0]), Math.abs(minSum[0]));
    }
}

解释

方法:

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

时间复杂度:

O(n * log(max(operate)))

空间复杂度:

O(1)

代码细节讲解

🦆
在`maybe`函数中,位掩码`mask`是如何精确地反映所有可能的湿度调整值的?是否有可能某些湿度调整值被错误地表示或遗漏?
在`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`是基于湿度调整的极端情况进行估计的。`min(operate)`提供了一个理论的最小范围,因为即使最小的操作也应当考虑。由于最大可能的湿度调整是在每次操作都是最大值的情况下发生的,`2 * max(operate)`考虑了这种连续两次操作可能导致的最大变动。加1是为了确保二分搜索的上限是闭区间,使得算法可以正确地处理边界值。这个范围确保了搜索空间足够大,能够覆盖所有可能的不适宜度值。
🦆
在二分搜索中,使用`maybe(d)`函数确定中间值时,具体是如何通过位操作模拟增加或减少湿度的效果?能否详细解释这一位操作的逻辑流程?
在`maybe(d)`函数中,位操作是通过左移和右移来模拟湿度的增加和减少。具体地,对于每一个操作值`x`,湿度的增加通过`u << x`表示,即将现有的可能湿度状态集合向左移动`x`位,表示每个可能的状态都增加了`x`单位的湿度。同理,湿度的减少通过`u >> x`表示,即向右移动`x`位。这两个操作的结果通过逻辑或操作`|`合并,表示任一增加或减少`x`单位湿度的可能性。最后,使用`& mask`操作确保结果仅包含在有效的位范围内,即去除因位移操作而超出范围的部分。这样,每次操作后,`u`都会更新为新的可能状态集合,直至遍历完所有操作。

相关问题