手写实现二分查找 bisect_left / lower_bound 和 bisect_right / upper_bound + 有序集合 TreeMap，顺序遍历 + 有序集合，2 解法求解《699. 掉落的方块》找第一个
找第一个
二分查找
找第一个 >= 目标数字的索引：bisect_left / lower_bound
const lower_bound = (nums, num) => {
let l = 0, r = nums.length - 1
while (l <= r) {
const m = l + r >> 1
if (nums[m] >= num) r = m - 1
else l = m + 1
}
return l
}func lower_bound(nums []int, num int) int { // 手写实现
l, r := 0, len(nums) - 1
for l <= r {
m := (l + r) >> 1
if nums[m] >= num {
r = m - 1
} else {
l = m + 1
}
}
return l
}func lower_bound(nums []int, num int) int { // sort.Search 实现
return sort.Search(len(nums), func(i int) bool {
return nums[i] >= num
})
}找第一个 > 目标数字的索引：bisect_right / upper_bound
const upper_bound = (nums, num) => {
let l = 0, r = nums.length - 1
while (l <= r) {
const m = l + r >> 1
if (nums[m] > num) r = m - 1
else l = m + 1
}
return l
}func upper_bound(nums []int, num int) int { // 手写实现
l, r := 0, len(nums) - 1
for l <= r {
m := (l + r) >> 1
if nums[m] > num {
r = m - 1
} else {
l = m + 1
}
}
return l
}func upper_bound(nums []int, num int) int { // sort.Search 实现
return sort.Search(len(nums), func(i int) bool {
return nums[i] > num
})
}JavaScript 有序集合 TreeMap 的实现
用 Object + 二分查找 / Map + Sort + 二分查找 实现
例题
699. 掉落的方块
在二维平面上的 x 轴上，放置着一些方块。
给你一个二维整数数组 positions ，其中 positions[i] = [lefti, sideLengthi] 表示：第 i 个方块边长为 sideLengthi ，其左侧边与 x 轴上坐标点 lefti 对齐。
每个方块都从一个比目前所有的落地方块更高的高度掉落而下。方块沿 y 轴负方向下落，直到着陆到 另一个正方形的顶边 或者是 x 轴上 。一个方块仅仅是擦过另一个方块的左侧边或右侧边不算着陆。一旦着陆，它就会固定在原地，无法移动。
在每个方块掉落后，你必须记录目前所有已经落稳的 方块堆叠的最高高度 。
返回一个整数数组 ans ，其中 ans[i] 表示在第 i 块方块掉落后堆叠的最高高度。
示例 1：
输入：positions = [[1,2],[2,3],[6,1]]
输出：[2,5,5]
解释：
第 1 个方块掉落后，最高的堆叠由方块 1 组成，堆叠的最高高度为 2 。
第 2 个方块掉落后，最高的堆叠由方块 1 和 2 组成，堆叠的最高高度为 5 。
第 3 个方块掉落后，最高的堆叠仍然由方块 1 和 2 组成，堆叠的最高高度为 5 。
因此，返回 [2, 5, 5] 作为答案。
答案
顺序遍历
var fallingSquares = function(positions) {
const n = positions.length, heights = new Uint32Array(n)
for (let i = 0; i < n; i++) {
const curLeft = positions[i][0], curHeight = positions[i][1], curRight = curLeft + curHeight
let height = curHeight
for (let j = 0; j < i; j++) {
const prevLeft = positions[j][0], prevRight = prevLeft + positions[j][1]
if (prevLeft < curRight && prevRight > curLeft) height = Math.max(height, heights[j] + curHeight)
}
heights[i] = height
}
for (let i = 1; i < n; i++) heights[i] = Math.max(heights[i], heights[i - 1])
return heights
};function fallingSquares(positions: number[][]): number[] {
const n = positions.length, heights = new Array(n)
for (let i = 0; i < n; i++) {
const curLeft = positions[i][0], curHeight = positions[i][1], curRight = curLeft + curHeight
let height = curHeight
for (let j = 0; j < i; j++) {
const prevLeft = positions[j][0], prevRight = prevLeft + positions[j][1]
if (prevLeft < curRight && prevRight > curLeft) height = Math.max(height, heights[j] + curHeight)
}
heights[i] = height
}
for (let i = 1; i < n; i++) heights[i] = Math.max(heights[i - 1], heights[i])
return heights
};class Solution {
function fallingSquares($positions) {
$n = count($positions);
$heights = array_fill(0, $n, 0);
foreach ($positions as $i => $position) {
$curLeft = $position[0];
$curHeight = $position[1];
$curRight = $curLeft + $curHeight;
$height = $curHeight;
for ($j = 0; $j < $i; $j++) {
$prevLeft = $positions[$j][0];
$prevRight = $prevLeft + $positions[$j][1];
if ($prevLeft < $curRight && $prevRight > $curLeft) {
$height = max($height, $heights[$j] + $curHeight);
}
}
$heights[$i] = $height;
}
for ($i = 1; $i < $n; $i++) $heights[$i] = max($heights[$i], $heights[$i - 1]);
return $heights;
}
}func fallingSquares(positions [][]int) []int {
n := len(positions)
heights := make([]int, n)
for i, position := range positions {
curLeft, curHeight, curRight := position[0], position[1], position[0] + position[1]
height := curHeight
for j := 0; j < i; j++ {
prevLeft, prevRight := positions[j][0], positions[j][0] + positions[j][1]
if prevLeft < curRight && prevRight > curLeft {
height = max(height, heights[j] + curHeight)
}
}
heights[i] = height
}
for i := 1; i < n; i++ {
heights[i] = max(heights[i], heights[i - 1])
}
return heights
}
func max(a, b int) int {
if a > b {
return a
}
return b
}class Solution:
def fallingSquares(self, positions: List[List[int]]) -> List[int]:
n = len(positions)
heights = [0] * n
for i, position in enumerate(positions):
curLeft, curHeight, curRight = position[0], position[1], position[0] + position[1]
height = curHeight
for j in range(0, i):
prevLeft, prevRight = positions[j][0], positions[j][0] + positions[j][1]
if prevLeft < curRight and prevRight > curLeft: height = max(height, heights[j] + curHeight)
heights[i] = height
for i in range(1, n):
heights[i] = max(heights[i - 1], heights[i])
return heightsclass Solution {
public List<Integer> fallingSquares(int[][] positions) {
int n = positions.length;
List<Integer> heights = new ArrayList<Integer>(n);
for (int i = 0; i < n; i++) {
int curLeft = positions[i][0];
int curHeight = positions[i][1];
int curRight = curLeft + curHeight;
int height = curHeight;
for (int j = 0; j < i; j++) {
int prevLeft = positions[j][0];
int prevRight = prevLeft + positions[j][1];
if (prevLeft < curRight && prevRight > curLeft) height = Math.max(height, heights.get(j) + curHeight);
}
heights.add(height);
}
for (int i = 1; i < n; i++) {
heights.set(i, Math.max(heights.get(i), heights.get(i - 1)));
}
return heights;
}
}有序集合 · 二分查找 · 一
var fallingSquares = function(positions) { // Object 实现
const treeMap = Object.create(null), n = positions.length, heights = new Uint32Array(n)
for (let i = 0; i < n; i++) {
const curLeft = positions[i][0], curHeight = positions[i][1], curRight = curLeft + curHeight
const sortedKeys = Object.keys(treeMap)
const l = upper_bound(sortedKeys, curLeft), r = lower_bound(sortedKeys, curRight)
const rightHeight = r > 0 ? treeMap[sortedKeys[r - 1]] : 0
let leftHeight = curHeight
for (let i = Math.max(l - 1, 0); i < r; i++) {
const sortedKey = sortedKeys[i]
leftHeight = Math.max(leftHeight, treeMap[sortedKey] + curHeight)
if (i >= l) delete treeMap[sortedKey]
}
treeMap[curLeft] = leftHeight
treeMap[curRight] = rightHeight
heights[i] = leftHeight
}
for (let i = 1; i < n; i++) heights[i] = Math.max(heights[i - 1], heights[i])
return heights
};
const upper_bound = (nums, num) => {
let l = 0, r = nums.length - 1
while (l <= r) {
const m = l + r >> 1
if (nums[m] > num) r = m - 1
else l = m + 1
}
return l
}
const lower_bound = (nums, num) => {
let l = 0, r = nums.length - 1
while (l <= r) {
const m = l + r >> 1
if (nums[m] >= num) r = m - 1
else l = m + 1
}
return l
}var fallingSquares = function(positions) { // Map 实现
const treeMap = new Map, n = positions.length, heights = new Uint32Array(n)
for (let i = 0; i < n; i++) {
const curLeft = positions[i][0], curHeight = positions[i][1], curRight = curLeft + curHeight
const sortedKeys = Array.from(treeMap.keys()).sort((a, b) => a - b)
const l = upper_bound(sortedKeys, curLeft), r = lower_bound(sortedKeys, curRight)
const rightHeight = r > 0 ? treeMap.get(sortedKeys[r - 1]) : 0
let leftHeight = curHeight
for (let i = Math.max(l - 1, 0); i < r; i++) {
const sortedKey = sortedKeys[i]
leftHeight = Math.max(leftHeight, treeMap.get(sortedKey) + curHeight)
if (i >= l) treeMap.delete(sortedKey)
}
treeMap.set(curLeft, leftHeight)
treeMap.set(curRight, rightHeight)
heights[i] = leftHeight
}
for (let i = 1; i < n; i++) heights[i] = Math.max(heights[i - 1], heights[i])
return heights
};
const upper_bound = (nums, num) => {
let l = 0, r = nums.length - 1
while (l <= r) {
const m = l + r >> 1
if (nums[m] > num) r = m - 1
else l = m + 1
}
return l
}
const lower_bound = (nums, num) => {
let l = 0, r = nums.length - 1
while (l <= r) {
const m = l + r >> 1
if (nums[m] >= num) r = m - 1
else l = m + 1
}
return l
}function fallingSquares(positions: number[][]): number[] { // Object 实现
const n = positions.length
const treeMap = Object.create(null)
const heights = new Array(n)
for (let i = 0; i < n; i++) {
const curLeft = positions[i][0], curHeight = positions[i][1], curRight = curLeft + curHeight
const sortedKeys = Object.keys(treeMap)
const l = upper_bound(sortedKeys, curLeft), r = lower_bound(sortedKeys, curRight)
const rightHeight = r > 0 ? treeMap[sortedKeys[r - 1]] : 0
let leftHeight = curHeight
for (let i = Math.max(l - 1, 0); i < r; i++) {
const sortedKey = sortedKeys[i]
leftHeight = Math.max(leftHeight, treeMap[sortedKey] + curHeight)
if (i >= l) delete treeMap[sortedKey]
}
treeMap[curLeft] = leftHeight
treeMap[curRight] = rightHeight
heights[i] = leftHeight
}
for (let i = 1; i < n; i++) heights[i] = Math.max(heights[i], heights[i - 1])
return heights
};
function upper_bound(nums: string[], num: number): number {
let l = 0, r = nums.length - 1
while (l <= r) {
const m = l + r >> 1
if (+nums[m] > num) r = m - 1
else l = m + 1
}
return l
}
function lower_bound(nums: string[], num: number): number {
let l = 0, r = nums.length - 1
while (l <= r) {
const m = l + r >> 1
if (+nums[m] >= num) r = m - 1
else l = m + 1
}
return l
}
class Solution {
function fallingSquares($positions) { // Array 实现
$n = count($positions);
$treeMap = array();
$heights = array_fill(0, $n, 0);
foreach ($positions as $i => $position) {
$curLeft = $position[0];
$curHeight = $position[1];
$curRight = $curLeft + $curHeight;
ksort($treeMap);
$sortedKeys = array_keys($treeMap);
$l = $this->upper_bound($sortedKeys, $curLeft);
$r = $this->lower_bound($sortedKeys, $curRight);
$rightHeight = $r > 0 ? $treeMap[$sortedKeys[$r - 1]] : 0;
$leftHeight = $curHeight;
for ($j = max($l - 1, 0); $j < $r; $j++) {
$sortedKey = $sortedKeys[$j];
$leftHeight = max($leftHeight, $treeMap[$sortedKey] + $curHeight);
if ($j >= $l) unset($treeMap[$sortedKey]);
}
$treeMap[$curLeft] = $leftHeight;
$treeMap[$curRight] = $rightHeight;
$heights[$i] = $leftHeight;
}
for ($i = 1; $i < $n; $i++) {
$heights[$i] = max($heights[$i], $heights[$i - 1]);
}
return $heights;
}
function upper_bound($nums, $num) {
$l = 0;
$r = count($nums) - 1;
while ($l <= $r) {
$m = $l + $r >> 1;
if ($nums[$m] > $num) $r = $m - 1;
else $l = $m + 1;
}
return $l;
}
function lower_bound($nums, $num) {
$l = 0;
$r = count($nums) - 1;
while ($l <= $r) {
$m = $l + $r >> 1;
if ($nums[$m] >= $num) $r = $m - 1;
else $l = $m + 1;
}
return $l;
}
}有序集合 · 二分查找 · 二
func fallingSquares(positions [][]int) []int { // 手写实现
n, treeMap := len(positions), map[int]int{}
heights := make([]int, n)
for i, position := range positions {
curLeft, curHeight, curRight := position[0], position[1], position[0] + position[1]
sortedKeys := getKeys(treeMap)
sort.Ints(sortedKeys)
l, r := upper_bound(sortedKeys, curLeft), lower_bound(sortedKeys, curRight)
rightHeight := 0
if r > 0 {
rightHeight = treeMap[sortedKeys[r - 1]]
}
leftHeight := curHeight
for j := max(l - 1, 0); j < r; j++ {
sortedKey := sortedKeys[j]
leftHeight = max(leftHeight, treeMap[sortedKey] + curHeight)
if j >= l {
delete(treeMap, sortedKey)
}
}
treeMap[curLeft] = leftHeight
treeMap[curRight] = rightHeight
heights[i] = leftHeight
}
for i := 1; i < n; i++ {
heights[i] = max(heights[i], heights[i - 1])
}
return heights
}
func getKeys(treeMap map[int]int) []int {
keys := make([]int, len(treeMap))
for key := range treeMap {
keys = append(keys, key)
}
return keys
}
func upper_bound(nums []int, num int) int {
l, r := 0, len(nums) - 1
for l <= r {
m := (l + r) >> 1
if nums[m] > num {
r = m - 1
} else {
l = m + 1
}
}
return l
}
func lower_bound(nums []int, num int) int {
l, r := 0, len(nums) - 1
for l <= r {
m := (l + r) >> 1
if nums[m] >= num {
r = m - 1
} else {
l = m + 1
}
}
return l
}
func max(a, b int) int {
if a > b {
return a
}
return b
}func fallingSquares(positions [][]int) []int { // sort.Search 实现
n, treeMap := len(positions), map[int]int{}
heights := make([]int, n)
for i, position := range positions {
curLeft, curHeight, curRight := position[0], position[1], position[0] + position[1]
sortedKeys := getKeys(treeMap)
sort.Ints(sortedKeys)
l, r := upper_bound(sortedKeys, curLeft), lower_bound(sortedKeys, curRight)
rightHeight := 0
if r > 0 {
rightHeight = treeMap[sortedKeys[r - 1]]
}
leftHeight := curHeight
for j := max(l - 1, 0); j < r; j++ {
sortedKey := sortedKeys[j]
leftHeight = max(leftHeight, treeMap[sortedKey] + curHeight)
if j >= l {
delete(treeMap, sortedKey)
}
}
treeMap[curLeft] = leftHeight
treeMap[curRight] = rightHeight
heights[i] = leftHeight
}
for i := 1; i < n; i++ {
heights[i] = max(heights[i], heights[i - 1])
}
return heights
}
func getKeys(treeMap map[int]int) []int {
keys := make([]int, len(treeMap))
for key := range treeMap {
keys = append(keys, key)
}
return keys
}
func upper_bound(nums []int, num int) int {
return sort.Search(len(nums), func(i int) bool {
return nums[i] > num
})
}
func lower_bound(nums []int, num int) int {
return sort.Search(len(nums), func(i int) bool {
return nums[i] >= num
})
}
func max(a, b int) int {
if a > b {
return a
}
return b
}class Solution: # Python 3
def fallingSquares(self, positions: List[List[int]]) -> List[int]:
n = len(positions)
treeMap, heights = {}, [0] * n
for i, position in enumerate(positions):
curLeft, curHeight, curRight = position[0], position[1], position[0] + position[1]
treeMap = collections.OrderedDict(sorted(treeMap.items(),key = lambda t:t[0]))
sortedKeys = list(treeMap.keys()) # Python 3 - list()
l, r = bisect.bisect_right(sortedKeys, curLeft), bisect.bisect_left(sortedKeys, curRight)
rightHeight = treeMap[sortedKeys[r - 1]] if r > 0 else 0
leftHeight = curHeight
for j in range(max(l - 1, 0), r):
sortedKey = sortedKeys[j]
leftHeight = max(leftHeight, treeMap[sortedKey] + curHeight)
if j >= l: del treeMap[sortedKey]
treeMap[curLeft] = leftHeight
treeMap[curRight] = rightHeight
heights[i] = leftHeight
for i in range(1, n): heights[i] = max(heights[i], heights[i - 1])
return heightsclass Solution(object): # Python
def fallingSquares(self, positions):
n = len(positions)
treeMap, heights = {}, [0] * n
for i, position in enumerate(positions):
curLeft, curHeight, curRight = position[0], position[1], position[0] + position[1]
treeMap = collections.OrderedDict(sorted(treeMap.items(),key = lambda t:t[0]))
sortedKeys = treeMap.keys()
l, r = bisect.bisect_right(sortedKeys, curLeft), bisect.bisect_left(sortedKeys, curRight)
rightHeight = treeMap[sortedKeys[r - 1]] if r > 0 else 0
leftHeight = curHeight
for j in range(max(l - 1, 0), r):
sortedKey = sortedKeys[j]
leftHeight = max(leftHeight, treeMap[sortedKey] + curHeight)
if j >= l: del treeMap[sortedKey]
treeMap[curLeft] = leftHeight
treeMap[curRight] = rightHeight
heights[i] = leftHeight
for i in range(1, n): heights[i] = max(heights[i], heights[i - 1])
return heights有序集合
class Solution {
public List<Integer> fallingSquares(int[][] positions) {
int n = positions.length;
TreeMap<Integer, Integer> treeMap = new TreeMap<Integer, Integer>();
List<Integer> heights = new ArrayList<Integer>(n);
for (int i = 0; i < n; i++) {
int curLeft = positions[i][0], curHeight = positions[i][1], curRight = curLeft + curHeight;
Integer leftKey = treeMap.higherKey(curLeft), rightKey = treeMap.higherKey(curRight - 1);
int leftHeight = curHeight, rightHeight = 0;
if (rightKey == null) {
if (treeMap.size() > 0) rightKey = treeMap.lastKey() + 1;
} else {
Integer prevRightKey = treeMap.lowerKey(rightKey - 1);
if (prevRightKey != null) rightHeight = treeMap.get(prevRightKey);
}
if (leftKey != null && rightKey != null) {
Integer prevLeftKey = treeMap.lowerKey(leftKey - 1);
if (prevLeftKey == null) prevLeftKey = treeMap.firstKey();
Set<Integer>keySet = new HashSet<Integer>();
Iterator<Integer>it = treeMap.subMap(prevLeftKey, rightKey).keySet().iterator();
while (it.hasNext()) keySet.add(it.next());
for (Integer sortedKey : keySet) {
leftHeight = Math.max(leftHeight, treeMap.get(sortedKey) + curHeight);
if (sortedKey >= leftKey) treeMap.remove(sortedKey);
}
}
treeMap.put(curLeft, leftHeight);
treeMap.put(curRight, rightHeight);
heights.add(leftHeight);
}
for (int i = 1; i < n; i++) {
heights.set(i, Math.max(heights.get(i), heights.get(i - 1)));
}
return heights;
}
}