移除所有载有违禁货物车厢所需的最少时间

难度: Hard

给你一个下标从 0 开始的二进制字符串 s ，表示一个列车车厢序列。s[i] = '0' 表示第 i 节车厢不含违禁货物，而 s[i] = '1' 表示第 i 节车厢含违禁货物。

作为列车长，你需要清理掉所有载有违禁货物的车厢。你可以不限次数执行下述三种操作中的任意一个：

从列车左端移除一节车厢（即移除 s[0]），用去 1 单位时间。
从列车右端移除一节车厢（即移除 s[s.length - 1]），用去 1 单位时间。
从列车车厢序列的 任意位置 移除一节车厢，用去 2 单位时间。

返回移除所有载有违禁货物车厢所需要的最少单位时间数。

注意，空的列车车厢序列视为没有车厢含违禁货物。

示例 1：

输入：s = "1100101"
输出：5
解释：
一种从序列中移除所有载有违禁货物的车厢的方法是：
- 从左端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。
- 从右端移除一节车厢 1 次。所用时间是 1 。
- 移除序列中间位置载有违禁货物的车厢。所用时间是 2 。
总时间是 2 + 1 + 2 = 5 。

一种替代方法是：
- 从左端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。
- 从右端移除一节车厢 3 次。所用时间是 3 * 1 = 3 。
总时间也是 2 + 3 = 5 。

5 是移除所有载有违禁货物的车厢所需要的最少单位时间数。
没有其他方法能够用更少的时间移除这些车厢。

示例 2：

输入：s = "0010"
输出：2
解释：
一种从序列中移除所有载有违禁货物的车厢的方法是：
- 从左端移除一节车厢 3 次。所用时间是 3 * 1 = 3 。
总时间是 3.

另一种从序列中移除所有载有违禁货物的车厢的方法是：
- 移除序列中间位置载有违禁货物的车厢。所用时间是 2 。
总时间是 2.

另一种从序列中移除所有载有违禁货物的车厢的方法是：
- 从右端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。
总时间是 2.

2 是移除所有载有违禁货物的车厢所需要的最少单位时间数。
没有其他方法能够用更少的时间移除这些车厢。

提示：

1 <= s.length <= 2 * 10⁵
s[i] 为 '0' 或 '1'

Submission

运行时间: 716 ms

内存: 17.1 MB

class Solution:
    def minimumTime(self, s: str) -> int:
        re = len(s)
        curmin = 0
        for i,ch in enumerate(s):
            if ch == '1':
                re = min(re,curmin+len(s)-i)
                curmin = min(curmin+2,i+1)
        return min(re,curmin)

Explain

此题解采用一种贪心策略，结合动态规划的思想，来找出移除所有违禁货物车厢所需的最少时间。算法思路包括计算两个主要值： 1. `re`：在处理到当前字符时，如果选择从左端或右端开始移除，到目前为止所需的最少时间。 2. `curmin`：在处理到当前字符时，如果选择从任意位置移除违禁货物车厢，到目前为止所需的最少时间。对于每个字符，如果是'0'（不含违禁货物），则直接继续；如果是'1'（含违禁货物），则计算两种策略的最小值：即从左端开始移除到当前位置，或者从当前位置向右移除。同时更新`curmin`为直接移除当前位置的车厢或保持之前的最小值（即在此之前的任何位置移除车厢）。最终，返回所有字符处理完毕后的最小值。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minimumTime(self, s: str) -> int:
        re = len(s)  # 初始化最小时间为字符串长度（即从一端移除所有车厢）
        curmin = 0  # 初始化从任意位置移除车厢的最小花费
        for i, ch in enumerate(s):
            if ch == '1':
                # 计算移除所有'1'的最小时间
                re = min(re, curmin + len(s) - i)
                # 更新从任意位置移除的最小花费
                curmin = min(curmin + 2, i + 1)
        # 返回处理完所有字符后的最小时间
        return min(re, curmin)

Explore

`curmin`变量在算法中非常关键，它记录了在当前迭代点之前，从任意位置开始移除车厢并处理到当前位置为止，所需的最小时间。在每次迭代中，如果当前字符为'1'（即包含违禁货物），则需要决定是继续保留之前的最小成本`curmin`，还是选择在当前位置新增一个移除操作（成本为2）。具体来说，`curmin`在每次迭代中通过`min(curmin + 2, i + 1)`进行更新。这里`curmin + 2`代表从前一字符的最佳位置继续处理，并增加2的成本（因为当前位置也是'1'），而`i + 1`代表从头开始直接移除到当前位置（包含当前位置）。这种更新确保了每个位置都考虑了从开始到当前位置的最低成本解决方案。

这行代码的目的是计算如果选择在当前位置或之前的某个位置处理完所有包含违禁货物的车厢，所需的总时间。`curmin`表示到当前位置前的任意位置处理完所需的最小时间，而`len(s) - i`代表从当前位置（包含）到字符串末尾的距离，即如果决定从当前位置开始向右移除所有车厢直到字符串末尾所需的操作数。因此，`curmin + len(s) - i`是一个综合考虑了从当前位置向右移除与之前的最优解的总成本。这一步的计算是为了找到一个全局最优，即整个字符串处理完毕时的最小时间。

贪心策略在此算法中体现在每次迭代时都尝试找到最小的成本解决方案。具体地说，每次遇到一个'1'时，算法会贪心地选择两个选项中的最小值：继续沿用之前的最小成本`curmin`，或者从当前位置开始新的移除操作。这种每步选择当前最优解的策略是贪心算法的特征。同时，通过动态地更新`curmin`和`re`来保持记录并最终得到全局的最优解，这反映了动态规划的特点，即基于子问题的最优解构建全局最优解。