P3161. 机房布局

解题思路

这道题有点类似于 种花问题 和 【贪心】2024D-座位调整/2024D-找座位 这类型的贪心问题，需要我们在有限的间隔或者空间中，找到所使用电箱数量最少的最优解。

非常强烈建议大家再回顾一下上述题目，并比较上述题目和本题的相似性和区别。

如何找到最佳的贪心策略

考虑一种简单的场景。对于以下例子：

对于第一个 M，我们既可以在第一个 I 的位置（第一个 M 的左边）装上电箱，也可以在第二个 I 的位置（第一个 M 的右边）装上电箱。 显然，我们在第二个 `I` 的位置装上电箱更加划算，因为这个电箱不仅靠近第一个 M，也可以靠近第二个 M。

因此，如果我们从左到右、从前到后来遍历整个 cabinets 字符串，每当遇到一个机器 M，当其左右两边都有空位 I 的时候，我们总是会优先在其右边的空位安装电箱，因为这样有可能使得我们装下的这个电箱能够同时给另一个机器 M 供电。

整体贪心策略

在从左到右对 cabinets 字符串遍历的过程中，提出如下贪心策略：

• 遇到 I 直接跳过，索引前进一步：index += 1
• 遇到 M 则考虑在其两侧中选择一侧装电箱

情况一：右侧有空位

如果 cabinets[index] == 'M' 的右边是一个空位 I，即 cabinets[index+1] == 'I' 成立：

• 立刻在 index+1 的位置进行电箱安装，ans += 1
• 安装后，index+2 的位置无论是 I 还是 M，都可以直接被跳过，因为如果 index+2 是 M 的话，也会被 index+1 处安装的电箱供电。
• 在这种情况下，index 可以前进三步，直接跳到 index+3 的位置，即 index += 3

情况二：右侧无空位，左侧有空位

如果 cabinets[index] == 'M' 的右边是一个机器 M，而其左边是一个空位 I，即 cabinets[index-1] == 'I' and cabinets[index+1] == 'M' 成立：

• 由于在上一种情况中（在 M 右侧安装电箱），我们安装了电箱后直接跳过了 I 后面的位置（index += 3），因此当这种情况出现时，M 左边的 I 一定没有安装电箱（可以用反证法证明）
• 直接在 index - 1 处安装电箱，index 前进一步到后面的机器 M 的位置，index += 1

情况三：左右两侧都是机器

如果 cabinets[index] == 'M' 的左右两边都是机器 M，则无法完成布局，修改 ans 为 -1 后退出循环。

代码框架

由于上述过程中 index 的前进步数不确定，因此需要在一个 while 循环中执行上述过程。整体代码框架如下：

避免越界的技巧

上述代码可能需要取用 index+1 和 index-1。为了避免写出冗余的关于越界判断的条件语句，常用的技巧是在原 cabinets 字符串的前后各自加上一个无关字符串，例如 "A"，这样可以有效地避免反复的越界判断。代码框架可以修改为：

注意：用了上述技巧之后，index 的初始化就要从 1 开始，而 while 的条件也要相应地修改为 index < n-1。同时，在条件语句中得用 cabinets[index-1] != "I" 和 cabinets[index+1] != "I" 来判断 index 的前后是否有空位。

完整代码实现

将上述代码框架中的 pass 内容进行填充，得到以下完整代码：

复杂度分析 设 n 为输入字符串 cabinets 的长度。

• 时间复杂度：O(n)。整个算法只有一个 while 循环，每一轮中 index 至少前进 1 步（遇到空位 I 前进 1 步；机器 M 右侧装电箱时一次前进 3 步），因此循环总轮数不超过 n，每轮内部只做常数次字符比较。遇到 M M M 这种无法供电的情形会把答案置为 -1 并提前 break，只会更快结束。
• 空间复杂度：O(n)。在原字符串前后各拼接一个哨兵字符 A，会产生一个长度为 n+2 的新字符串副本；除此之外只用了 index、ans 等常数个变量。