Medium

题目描述

有一个 m x n 的网格，其中 (0, 0) 是左上角单元格，(m - 1, n - 1) 是右下角单元格。给你一个整数数组 startPos，其中 startPos = [startrow, startcol] 表示机器人最初位于单元格 (startrow, startcol)。另给你一个整数数组 homePos，其中 homePos = [homerow, homecol] 表示机器人的家位于单元格 (homerow, homecol)。

机器人需要回到家中。它可以向四个方向移动：左、右、上或下，但不能移出边界。每次移动都会产生一些代价。另外给你两个下标从 0 开始的整数数组：长度为 m 的 rowCosts 和长度为 n 的 colCosts。

  • 如果机器人向上或向下移动到行为 r 的单元格，则此移动的代价为 rowCosts[r]。
  • 如果机器人向左或向右移动到列为 c 的单元格，则此移动的代价为 colCosts[c]。

返回机器人回家的最小总代价。

示例 1：

输入：startPos = [1, 0], homePos = [2, 3], rowCosts = [5, 4, 3], colCosts = [8, 2, 6, 7]
输出：18
解释：一条最优路径为：
从 (1, 0) 开始
-> 向下移动到 (2, 0)。此移动的代价为 rowCosts[2] = 3。
-> 向右移动到 (2, 1)。此移动的代价为 colCosts[1] = 2。
-> 向右移动到 (2, 2)。此移动的代价为 colCosts[2] = 6。
-> 向右移动到 (2, 3)。此移动的代价为 colCosts[3] = 7。
总代价为 3 + 2 + 6 + 7 = 18

示例 2：

输入：startPos = [0, 0], homePos = [0, 0], rowCosts = [5], colCosts = [26]
输出：0
解释：机器人已经在家中。由于没有发生移动，总代价为 0。

约束条件：

  • m == rowCosts.length
  • n == colCosts.length
  • 1 <= m, n <= 10^5
  • 0 <= rowCosts[r], colCosts[c] <= 10^4
  • startPos.length == 2
  • homePos.length == 2
  • 0 <= startrow, homerow < m
  • 0 <= startcol, homecol < n

解题思路

解题思路

这是一道贪心算法题。关键洞察是：无论机器人选择什么路径，它都必须经过起始位置和目标位置之间的所有行和列。

贪心策略分析

  1. 必经路径：机器人必须从起始行移动到目标行，从起始列移动到目标列，这些移动是不可避免的。

  2. 最优策略：任何绕路的移动都会增加额外的代价，因此最优策略是直接走最短路径。

  3. 代价计算：

    • 行移动代价：计算从 startRow 到 homeRow 之间所有行的代价总和
    • 列移动代价：计算从 startCol 到 homeCol 之间所有列的代价总和

实现细节

  • 使用区间求和计算行代价和列代价
  • 注意处理起始位置和目标位置的相对关系（可能需要向上/下或向左/右移动）
  • 当起始位置和目标位置相同时，不产生任何代价

这种贪心策略是最优的，因为任何偏离直接路径的移动都会产生额外且不必要的代价。

代码实现

class Solution {
public:
    int minCost(vector<int>& startPos, vector<int>& homePos, vector<int>& rowCosts, vector<int>& colCosts) {
        int startRow = startPos[0], startCol = startPos[1];
        int homeRow = homePos[0], homeCol = homePos[1];
        
        int totalCost = 0;
        
        // 计算行移动代价
        int minRow = min(startRow, homeRow);
        int maxRow = max(startRow, homeRow);
        for (int r = minRow; r <= maxRow; r++) {
            if (r != startRow) { // 不计算起始位置的代价
                totalCost += rowCosts[r];
            }
        }
        
        // 计算列移动代价
        int minCol = min(startCol, homeCol);
        int maxCol = max(startCol, homeCol);
        for (int c = minCol; c <= maxCol; c++) {
            if (c != startCol) { // 不计算起始位置的代价
                totalCost += colCosts[c];
            }
        }
        
        return totalCost;
    }
};

class Solution:
    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:
        start_row, start_col = startPos
        home_row, home_col = homePos
        
        total_cost = 0
        
        # 计算行移动代价
        min_row = min(start_row, home_row)
        max_row = max(start_row, home_row)
        for r in range(min_row, max_row + 1):
            if r != start_row:  # 不计算起始位置的代价
                total_cost += rowCosts[r]
        
        # 计算列移动代价
        min_col = min(start_col, home_col)
        max_col = max(start_col, home_col)
        for c in range(min_col, max_col + 1):
            if c != start_col:  # 不计算起始位置的代价
                total_cost += colCosts[c]
        
        return total_cost

public class Solution {
    public int MinCost(int[] startPos, int[] homePos, int[] rowCosts, int[] colCosts) {
        int startRow = startPos[0], startCol = startPos[1];
        int homeRow = homePos[0], homeCol = homePos[1];
        
        int totalCost = 0;
        
        // 计算行移动代价
        int minRow = Math.Min(startRow, homeRow);
        int maxRow = Math.Max(startRow, homeRow);
        for (int r = minRow; r <= maxRow; r++) {
            if (r != startRow) { // 不计算起始位置的代价
                totalCost += rowCosts[r];
            }
        }
        
        // 计算列移动代价
        int minCol = Math.Min(startCol, homeCol);
        int maxCol = Math.Max(startCol, homeCol);
        for (int c = minCol; c <= maxCol; c++) {
            if (c != startCol) { // 不计算起始位置的代价
                totalCost += colCosts[c];
            }
        }
        
        return totalCost;
    }
}

var minCost = function(startPos, homePos, rowCosts, colCosts) {
    const [startRow, startCol] = startPos;
    const [homeRow, homeCol] = homePos;
    
    let totalCost = 0;
    
    // 计算行移动代价
    const minRow = Math.min(startRow, homeRow);
    const maxRow = Math.max(startRow, homeRow);
    for (let r = minRow; r <= maxRow; r++) {
        if (r !== startRow) { // 不计算起始位置的代价
            totalCost += rowCosts[r];
        }
    }
    
    // 计算列移动代价
    const minCol = Math.min(startCol, homeCol);
    const maxCol = Math.max(startCol, homeCol);
    for (let c = minCol; c <= maxCol; c++) {
        if (c !== startCol) { // 不计算起始位置的代价
            totalCost += colCosts[c];
        }
    }
    
    return totalCost;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(|startRow - homeRow| + |startCol - homeCol|)需要遍历起始位置到目标位置之间的所有行和列
空间复杂度O(1)只使用常数额外空间

相关题目