LeetCode 853. 车队

Categories:

题目描述
思路分析
1. 解法一：排序 + 单调栈思想（推荐）
相似题目

题目描述

✅ 853. 车队

思路分析

解法一：排序 + 单调栈思想（推荐）

核心思路：

按位置从近到远排序（位置降序）。

计算每辆车到终点的时间，若时间大于当前最大时间则形成新车队。

否则并入前方车队。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示车辆数量。

空间复杂度：O(n)。

import java.util.Arrays;

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        int[][] cars = new int[n][2];
        for (int i = 0; i < n; i++) {
            cars[i][0] = position[i];
            cars[i][1] = speed[i];
        }

        Arrays.sort(cars, (a, b) -> b[0] - a[0]);

        int fleets = 0;
        double maxTime = 0;
        for (int[] car : cars) {
            double time = (double) (target - car[0]) / car[1];
            if (time > maxTime) {
                fleets++;
                maxTime = time;
            }
        }

        return fleets;
    }
}

import "sort"

func carFleet(target int, position []int, speed []int) int {
	n := len(position)
	cars := make([][2]int, n)
	for i := 0; i < n; i++ {
		cars[i] = [2]int{position[i], speed[i]}
	}

	sort.Slice(cars, func(i, j int) bool {
		return cars[i][0] > cars[j][0]
	})

	fleets := 0
	maxTime := 0.0
	for _, car := range cars {
		time := float64(target-car[0]) / float64(car[1])
		if time > maxTime {
			fleets++
			maxTime = time
		}
	}

	return fleets
}

相似题目

题目	难度	考察点
1776. 车队 II	困难	单调栈
456. 132 模式	中等	单调栈
853. 车队	中等	排序
1696. 跳跃游戏 VI	中等	单调队列
239. 滑动窗口最大值	困难	单调队列

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/44245775