可以到达的最远建筑

1642. 可以到达的最远建筑

给你一个整数数组 heights ，表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders 。

你从建筑物 0 开始旅程，不断向后面的建筑物移动，期间可能会用到砖块或梯子。

当从建筑物 i 移动到建筑物 i+1（下标 从 0 开始 ）时：

如果当前建筑物的高度 大于或等于 下一建筑物的高度，则不需要梯子或砖块
如果当前建筑的高度小于下一个建筑的高度，您可以使用 一架梯子 或 (h[i+1] - h[i]) 个砖块

如果以最佳方式使用给定的梯子和砖块，返回你可以到达的最远建筑物的下标（下标 从 0 开始 ）。

示例 1：

输入：heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
输出：4
解释：从建筑物 0 出发，你可以按此方案完成旅程：
- 不使用砖块或梯子到达建筑物 1 ，因为 4 >= 2
- 使用 5 个砖块到达建筑物 2 。你必须使用砖块或梯子，因为 2 < 7
- 不使用砖块或梯子到达建筑物 3 ，因为 7 >= 6
- 使用唯一的梯子到达建筑物 4 。你必须使用砖块或梯子，因为 6 < 9
无法越过建筑物 4 ，因为没有更多砖块或梯子。

示例 2：

输入：heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
输出：7

示例 3：

输入：heights = [14,3,19,3], bricks = 17, ladders = 0
输出：3

提示：

1 <= heights.length <= 10⁵
1 <= heights[i] <= 10⁶
0 <= bricks <= 10⁹
0 <= ladders <= heights.length

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int furthestBuilding(vector<int>& heights, int bricks, int ladders) { } };

python3 解法, 执行用时: 136 ms, 内存消耗: 26.8 MB, 提交时间: 2023-09-26 20:05:56

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        n = len(heights)
        # 由于我们需要维护最大的 l 个值，因此使用小根堆
        q = list()
        # 需要使用砖块的 delta h 的和
        sumH = 0
        for i in range(1, n):
            deltaH = heights[i] - heights[i - 1]
            if deltaH > 0:
                heapq.heappush(q, deltaH)
                # 如果优先队列已满，需要拿出一个其中的最小值，改为使用砖块
                if len(q) > ladders:
                    sumH += heapq.heappop(q)
                if sumH > bricks:
                    return i - 1
        return n - 1

cpp 解法, 执行用时: 96 ms, 内存消耗: 52.7 MB, 提交时间: 2023-09-26 20:05:46

class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        int n = heights.size();
        // 由于我们需要维护最大的 l 个值，因此使用小根堆
        priority_queue<int, vector<int>, greater<int>> q;
        // 需要使用砖块的 delta h 的和
        int sumH = 0;
        for (int i = 1; i < n; ++i) {
            int deltaH = heights[i] - heights[i - 1];
            if (deltaH > 0) {
                q.push(deltaH);
                // 如果优先队列已满，需要拿出一个其中的最小值，改为使用砖块
                if (q.size() > ladders) {
                    sumH += q.top();
                    q.pop();
                }
                if (sumH > bricks) {
                    return i - 1;
                }
            }
        }
        return n - 1;
    }
};

java 解法, 执行用时: 20 ms, 内存消耗: 55.6 MB, 提交时间: 2023-09-26 20:05:15

class Solution {
    // 贪心 + 堆
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        int n = heights.length, sum = 0;
        Queue<Integer> queue = new PriorityQueue<>();
        for(int i = 1; i < heights.length; i++) {
            int diff = heights[i] - heights[i - 1];
            if(diff > 0) {
                queue.offer(diff);
                if(queue.size() > ladders) {
                    sum += queue.poll();
                }
                if(sum > bricks)
                    return i - 1;
            }
        }
        return n - 1;
    }


    // 二分查找
    public int furthestBuilding2(int[] heights, int bricks, int ladders) {
        int l = ladders, r = heights.length - 1;
        while(l <= r) {
            int mid = l + r >>> 1;
            if(check(heights, bricks, ladders, mid))
                l = mid + 1;
            else
                r = mid - 1;
        }
        return r;
    }
    
    private boolean check(int[] heights, int bricks, int ladders, int n) {
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            if(heights[i + 1] - heights[i] > 0) {
                list.add(heights[i + 1] - heights[i]);
            }
        }
        Collections.sort(list);
        int sum = 0;
        for(int i = 0; i < list.size() - ladders; i ++) {
            sum += list.get(i);
            if(sum > bricks)
                return false;
        }
        return true;
    }

    // dfs
    private int ans = 0;
    public int furthestBuilding3(int[] heights, int bricks, int ladders) {
        dfs(heights, 0, bricks, ladders);
        return ans;
    }
    private void dfs(int[] heights, int cur, int bricks, int ladders) {
        if(ans == heights.length - 1) //这句剪枝是关键，缺少这一句，会超时。
            return;
        if(cur == heights.length - 1 || (heights[cur + 1] - heights[cur] > bricks && ladders == 0)) {
            ans = Math.max(ans, cur);
            return;
        }
        if(heights[cur] >= heights[cur + 1])
            dfs(heights, cur + 1, bricks, ladders);
        else{
            if(bricks >= heights[cur + 1] - heights[cur])
                dfs(heights, cur + 1, bricks + heights[cur] - heights[cur + 1], ladders);
            if(ladders >= 1)
                dfs(heights, cur + 1, bricks, ladders - 1);
        }
            
    }
}

golang 解法, 执行用时: 300 ms, 内存消耗: 8.6 MB, 提交时间: 2023-09-26 20:03:00

// 二分搜索
func furthestBuilding(heights []int, bricks int, ladders int) int {
	l, r := 0, len(heights)
	res := 0
	for l <= r {
		mid := (l + r) >> 1
		if check(heights[0:mid], bricks, ladders) {
			l = mid + 1
			res = mid
		}else {
			r = mid - 1
		}
	}
	return res - 1
}

func check(heights []int, bricks int, ladders int) bool{
	needBricks := []int{}
	for i := 1; i < len(heights); i++ {
		tempNeed := heights[i] - heights[i - 1]
		if tempNeed > 0 {
			needBricks = append(needBricks, tempNeed)
		}
	}
	sort.Ints(needBricks)
	i := 0
	for ; i < len(needBricks); i++ {
		if tb := bricks - needBricks[i]; tb >= 0 {
			bricks = tb
			continue
		}
		if ladders > 0 {
			ladders --
			continue
		}
		break
	}
	return i == len(needBricks)
}

rust 解法, 执行用时: 12 ms, 内存消耗: 3.1 MB, 提交时间: 2023-09-26 20:02:25

impl Solution {
    pub fn furthest_building(heights: Vec<i32>, bricks: i32, ladders: i32) -> i32 {
        if heights.len() <= 1 {
            return 0;
        }

        let mut bricks = bricks;
        let mut min_heap = std::collections::BinaryHeap::new();

        for i in 1..heights.len(){

            let dif = heights[i]-heights[i-1];
            if dif <=0{
                continue
            }
            min_heap.push(std::cmp::Reverse(dif));
            //梯子数量不够了,把之前差值最小的换为砖块
            if min_heap.len() as i32 > ladders{
                if let Some(std::cmp::Reverse(mid_dif)) = min_heap.pop(){

                    //到目前位置 梯子都用于最高的几次跳跃了，砖块却不够
                    if mid_dif>bricks{
                        return i as i32 -1
                    }

                    bricks = bricks - mid_dif;

                } 
            }
        }

        heights.len() as i32 - 1
    }
}

golang 解法, 执行用时: 80 ms, 内存消耗: 9.4 MB, 提交时间: 2023-09-26 20:02:11

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) {
	// Push and Pop use pointer receivers because they modify the slice's length,
	// not just its contents.
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

/*
 先都使用梯子，梯子不够的时候，取出高度差最小的使用砖头
*/
func furthestBuilding(heights []int, bricks int, ladders int) int {

	if len(heights) <= 1 {
		return 0
	}

	h := &IntHeap{}
	heap.Init(h)
	dif := 0
	for i := 1; i < len(heights); i++ {
		dif = heights[i] - heights[i-1]
		if dif <= 0 {
			continue
		}

		heap.Push(h, dif)
		//梯子不够了,取出最小的高度差 使用砖头
		if h.Len() > ladders {
			dif = heap.Pop(h).(int)
			if dif > bricks {
				return i - 1 //这里是要减去一，因为当前的位置砖头已经不够了
			}
			bricks -= dif
		}

	}

	return len(heights) - 1
}

php 解法, 执行用时: 152 ms, 内存消耗: 30.9 MB, 提交时间: 2023-09-26 20:01:32

class Solution {

    /**
     * @param Integer[] $heights
     * @param Integer $bricks
     * @param Integer $ladders
     * @return Integer
     */
    function furthestBuilding($heights, $bricks, $ladders) {
        $hp = new SplMaxHeap;
        $n = count($heights);
        $totb = 0;
        for ($i = 0; $i + 1 < $n; ++$i) {
            if ($heights[$i] >= $heights[$i + 1]) continue;
            $diff = $heights[$i + 1] - $heights[$i];
            $totb += $diff;
            $hp->insert($diff);
            while ($hp->count() && $totb > $bricks && $ladders > 0) {
                $totb -= $hp->extract();
                $ladders--;
            }
            if ($totb > $bricks && $ladders <= 0) break;
        }
        return $i;
    }
}

上一题

下一题

详情