Hard

题目描述

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

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

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

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

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

示例 1：

输入：s = "1100101"
输出：5
解释：
移除所有载有违禁货物的车厢的一种方法是：
- 从左端移除一节车厢 2 次。用去时间 2 * 1 = 2 。
- 从右端移除一节车厢。用去时间 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^5
  • s[i] 为 '0' 或 '1'

解题思路

这是一道典型的动态规划问题。核心思路是将问题分解为两部分：左侧前缀用操作1（从左端移除）处理，右侧后缀用操作2（从右端移除）或操作3（中间移除）处理。

解题思路：

  1. 建立两个数组来表示不同策略的最小代价：

    • left[i]：表示处理前缀 s[0...i] 只使用操作1的最小时间
    • right[i]：表示处理后缀 s[i...n-1] 不使用操作1的最小时间

  2. 计算left数组： 对于前缀，我们只能从左端依次移除，所以 left[i] = i + 1

  3. 计算right数组： 这里使用动态规划的关键思想

    • 如果 s[i] == '0'：当前车厢无违禁货物，right[i] = right[i+1]
    • 如果 s[i] == '1'：当前车厢有违禁货物，有两种选择：
      • 中间移除：代价为 2 + right[i+1]
      • 右端移除：将当前位置及右侧全部移除，代价为 n - i
      • 取两者最小值：right[i] = min(2 + right[i+1], n - i)

  4. 枚举分割点： 最终答案为所有可能分割方案中的最小值：min(left[i] + right[i+1]) 对所有有效的i

时间复杂度： O(n)，需要遍历字符串两次 空间复杂度： O(n)，需要额外的数组存储中间结果

这种方法巧妙地将复杂的三种操作组合问题转化为了简单的前缀-后缀分割问题，是解决此类问题的经典思路。

代码实现

class Solution {
public:
    int minimumTime(string s) {
        int n = s.length();
        vector<int> left(n), right(n + 1);
        
        // 计算left数组：前缀只用操作1的代价
        for (int i = 0; i < n; i++) {
            left[i] = i + 1;
        }
        
        // 计算right数组：后缀不用操作1的代价
        right[n] = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == '0') {
                right[i] = right[i + 1];
            } else {
                right[i] = min(2 + right[i + 1], n - i);
            }
        }
        
        // 枚举所有分割点
        int result = right[0]; // 全部用操作2和3
        for (int i = 0; i < n; i++) {
            result = min(result, left[i] + right[i + 1]);
        }
        
        return result;
    }
};

class Solution:
    def minimumTime(self, s: str) -> int:
        n = len(s)
        left = [0] * n
        right = [0] * (n + 1)
        
        # 计算left数组：前缀只用操作1的代价
        for i in range(n):
            left[i] = i + 1
        
        # 计算right数组：后缀不用操作1的代价
        right[n] = 0
        for i in range(n - 1, -1, -1):
            if s[i] == '0':
                right[i] = right[i + 1]
            else:
                right[i] = min(2 + right[i + 1], n - i)
        
        # 枚举所有分割点
        result = right[0]  # 全部用操作2和3
        for i in range(n):
            result = min(result, left[i] + right[i + 1])
        
        return result

public class Solution {
    public int MinimumTime(string s) {
        int n = s.Length;
        int[] left = new int[n];
        int[] right = new int[n + 1];
        
        // 计算left数组：前缀只用操作1的代价
        for (int i = 0; i < n; i++) {
            left[i] = i + 1;
        }
        
        // 计算right数组：后缀不用操作1的代价
        right[n] = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == '0') {
                right[i] = right[i + 1];
            } else {
                right[i] = Math.Min(2 + right[i + 1], n - i);
            }
        }
        
        // 枚举所有分割点
        int result = right[0]; // 全部用操作2和3
        for (int i = 0; i < n; i++) {
            result = Math.Min(result, left[i] + right[i + 1]);
        }
        
        return result;
    }
}

var minimumTime = function(s) {
    const n = s.length;
    const left = new Array(n);
    const right = new Array(n + 1);
    
    // 计算left数组：前缀只用操作1的代价
    for (let i = 0; i < n; i++) {
        left[i] = i + 1;
    }
    
    // 计算right数组：后缀不用操作1的代价
    right[n] = 0;
    for (let i = n - 1; i >= 0; i--) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n)
空间复杂度O(n)

其中 n 是字符串 s 的长度。时间复杂度为 O(n) 是因为需要遍历字符串两次来计算 left 和 right 数组，然后再遍历一次来找最小值。空间复杂度为 O(n) 是因为需要额外的 left 和 right 数组来存储中间结果。

相关题目