furthest-building-you-can-reach

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an integer array <code>heights</code> representing the heights of buildings, some <code>bricks</code>, and some <code>ladders</code>.

You start your journey from building <code>0</code> and move to the next building by possibly using bricks or ladders.

While moving from building <code>i</code> to building <code>i+1</code> (0-indexed),

<ul>
	<li>If the current building&#39;s height is greater than or equal to the next building&#39;s height, you do not need a ladder or bricks.</li>
	<li>If the current building&#39;s height is less than the next building&#39;s height, you can either use one ladder or <code>(h[i+1] - h[i])</code> bricks.</li>
</ul>

Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2020/10/27/q4.gif" style="width: 562px; height: 561px;" />
<pre>
Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
Output: 4
Explanation: Starting at building 0, you can follow these steps:
- Go to building 1 without using ladders nor bricks since 4 &gt;= 2.
- Go to building 2 using 5 bricks. You must use either bricks or ladders because 2 &lt; 7.
- Go to building 3 without using ladders nor bricks since 7 &gt;= 6.
- Go to building 4 using your only ladder. You must use either bricks or ladders because 6 &lt; 9.
It is impossible to go beyond building 4 because you do not have any more bricks or ladders.
</pre>

Example 2:

<pre>
Input: heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
Output: 7
</pre>

Example 3:

<pre>
Input: heights = [14,3,19,3], bricks = 17, ladders = 0
Output: 3
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= heights.length &lt;= 105</code></li>
	<li><code>1 &lt;= heights[i] &lt;= 106</code></li>
	<li><code>0 &lt;= bricks &lt;= 109</code></li>
	<li><code>0 &lt;= ladders &lt;= heights.length</code></li>
</ul>

furthestBuilding

Furthest Building You Can Reach

Make the Prefix Sum Non-negative

make-the-prefix-sum-non-negative

使前缀和数组非负

Find Building Where Alice and Bob Can Meet

find-building-where-alice-and-bob-can-meet

找到 Alice 和 Bob 可以相遇的建筑

Greedy

Array

Heap (Priority Queue)

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

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

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

<ul>
	<li>如果当前建筑物的高度 大于或等于 下一建筑物的高度，则不需要梯子或砖块</li>
	<li>如果当前建筑的高度 小于 下一个建筑的高度，您可以使用 一架梯子 或 <code>(h[i+1] - h[i])</code> 个砖块</li>
</ul>
如果以最佳方式使用给定的梯子和砖块，返回你可以到达的最远建筑物的下标（下标 从 0 开始 ）。

 

示例 1：
<img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/10/31/q4.gif" style="width: 562px; height: 561px;" />
<pre>
输入：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 ，因为没有更多砖块或梯子。
</pre>

示例 2：

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

示例 3：

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

 

提示：

<ul>
	<li><code>1 <= heights.length <= 105</code></li>
	<li><code>1 <= heights[i] <= 106</code></li>
	<li><code>0 <= bricks <= 109</code></li>
	<li><code>0 <= ladders <= heights.length</code></li>
</ul>