贪心

分发饼干

大饼干分给大胃口

function findContentChildren(g: number[], s: number[]): number {
    g.sort((a, b) => b - a)
    s.sort((a, b) => b - a)
    let i = 0
    for (let v of g) {
        if (v <= s[i]) i++
    }
    return i
};

无重叠区间

按区间终点升序排列
删除重叠区间

function eraseOverlapIntervals(intervals: number[][]): number {
    intervals.sort((a, b) => a[1] - b[1])
    let prev = intervals[0]
    let count = 0
    for (let curr of intervals.slice(1)) {
        if (curr[0] < prev[1]) count++ // 区间重叠
        else prev = curr
    }
    return count
};

用最少数量的箭引爆气球

最少箭数 = 区间总数 - 重叠区间数

function findMinArrowShots(points: number[][]): number {
    points.sort((a, b) => a[1] - b[1])
    let prev = points[0]
    let count = 0
    for (let curr of points.slice(1)) {
        if (curr[0] <= prev[1]) count++ // 区间重叠
        else prev = curr
    }
    return points.length - count
};

买卖股票的最佳时机

当前最大利润 = 当前价格 - 历史最低价

function maxProfit(prices: number[]): number {
    let minPrice = prices[0]
    let maxProfit = 0
    for (let currPrice of prices.slice(1)) {
        minPrice = Math.min(minPrice, currPrice)
        maxProfit = Math.max(maxProfit, currPrice - minPrice)
    }
    return maxProfit
};

买卖股票的最佳时机 II

$p_4 - p_1 = (p_4 - p_3) + (p_3 - p_2) + (p_2 - p_1)$

每天涨了就买，亏了就跳过

function maxProfit(prices: number[]): number {
    let maxProfit = 0
    for (let i = 1; i < prices.length; i++) {
        let profit = prices[i] - prices[i - 1]
        if (profit > 0) maxProfit += profit
    }
    return maxProfit
};

跳跃游戏

不断更新能跳到的最远距离

function canJump(nums: number[]): boolean {
    let maxDistance = 1
    for (let i = 0; i < maxDistance; i++) {
        maxDistance = Math.max(maxDistance, i + nums[i] + 1)
        if (maxDistance >= nums.length) return true
    }
    return false
};

跳跃游戏 II

记录每一步能跳到的最远距离

function jump(nums: number[]): number {
    let maxDistance = 1 // 当前能跳到的最远距离
    let stepCount = 0
 
    while (maxDistance < nums.length) {
        let distances = nums.slice(0, maxDistance).map((v, i) => v + i + 1)
        maxDistance = Math.max(...distances)
        stepCount++
    }
    return stepCount
};

种花问题

只能在 [0, 0, 0] 中间种花

function canPlaceFlowers(flowerbed: number[], n: number): boolean {
    flowerbed.push(0)
    flowerbed.unshift(0)
    
    let count = 0
    for (let i = 0; i <= flowerbed.length - 3; i++) {
        if (flowerbed.slice(i, i + 3).join('') === '000') {
            flowerbed[i + 1] = 1
            count++
        }
    }
 
    return  count >= n
};