Medium

题目描述

给你一个严格递增的整数数组 rungs，表示梯子上横档的高度。你目前在地面上，高度为 0，你想要到达最后一个横档。

同时给你一个整数 dist。当你目前所在位置（地面或某个横档）与下一个横档之间的距离 不超过 dist 时，你才能爬到下一个更高的横档。你可以在任何正整数高度处插入横档（如果该位置没有横档）。

返回使你能够爬到最后一个横档所需要添加的 最少横档数目。

示例 1：

输入：rungs = [1,3,5,10], dist = 2
输出：2
解释：
你目前无法到达最后一个横档。
在高度为 7 和 8 的位置增加横档来爬这个梯子。
梯子在高度为 [1,3,5,7,8,10] 的位置上有横档。

示例 2：

输入：rungs = [3,6,8,10], dist = 3
输出：0
解释：
这个梯子无需增加横档即可爬上去。

示例 3：

输入：rungs = [3,4,6,7], dist = 2
输出：1
解释：
你目前无法从地面到达第一个横档。
在高度为 1 的位置增加一个横档来爬这个梯子。
梯子在高度为 [1,3,4,6,7] 的位置上有横档。

提示：

  • 1 <= rungs.length <= 10^5
  • 1 <= rungs[i] <= 10^9
  • 1 <= dist <= 10^9
  • rungs 严格递增

解题思路

这是一道典型的贪心算法题。我们需要找出在现有梯子横档之间需要添加多少个横档，使得每两个相邻横档（包括地面到第一个横档）的距离都不超过 dist。

核心思路：

  1. 贪心策略：当两个相邻位置间距超过 dist 时，我们需要在它们之间添加横档。为了最小化添加的横档数量，应该让每个新添加的横档都尽可能高，即每两个横档间的距离都恰好等于 dist。

  2. 计算公式：对于两个位置间距为 gap 的情况，需要添加的横档数量为 (gap - 1) / dist。这个公式的含义是：

    • 如果 gap <= dist，则不需要添加横档
    • 如果 gap > dist，则需要添加 ⌊(gap-1)/dist⌋ 个横档

  3. 遍历过程：从地面（高度0）开始，依次检查到每个横档的距离，累加需要添加的横档数量。

算法步骤：

  1. 初始化当前位置为0（地面）
  2. 遍历每个横档，计算当前位置到该横档的距离
  3. 如果距离超过 dist，计算需要添加的横档数并累加到结果中
  4. 更新当前位置为该横档位置
  5. 返回总的添加横档数

代码实现

class Solution {
public:
    int addRungs(vector<int>& rungs, int dist) {
        int result = 0;
        int currentPos = 0;
        
        for (int rung : rungs) {
            int gap = rung - currentPos;
            if (gap > dist) {
                result += (gap - 1) / dist;
            }
            currentPos = rung;
        }
        
        return result;
    }
};

class Solution:
    def addRungs(self, rungs: List[int], dist: int) -> int:
        result = 0
        current_pos = 0
        
        for rung in rungs:
            gap = rung - current_pos
            if gap > dist:
                result += (gap - 1) // dist
            current_pos = rung
        
        return result

public class Solution {
    public int AddRungs(int[] rungs, int dist) {
        int result = 0;
        int currentPos = 0;
        
        foreach (int rung in rungs) {
            int gap = rung - currentPos;
            if (gap > dist) {
                result += (gap - 1) / dist;
            }
            currentPos = rung;
        }
        
        return result;
    }
}

/**
 * @param {number[]} rungs
 * @param {number} dist
 * @return {number}
 */
var addRungs = function(rungs, dist) {
    let result = 0;
    let currentPos = 0;
    
    for (let rung of rungs) {
        let gap = rung - currentPos;
        if (gap > dist) {
            result += Math.floor((gap - 1) / dist);
        }
        currentPos = rung;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历所有横档一次，n 为 rungs 数组长度
空间复杂度O(1)只使用了常数个额外变量

相关题目