LeetCode 面试题 17.08. 马戏团人塔

Categories:

题目描述
思路分析
1. 解法一：排序 + 最长递增子序列（推荐）
相似题目

题目描述

✅ 面试题 17.08. 马戏团人塔

思路分析

解法一：排序 + 最长递增子序列（推荐）

核心思路：

先按身高升序、体重降序排序，避免相同身高被错误串成递增序列。

问题转化为在体重序列上求严格递增的最长子序列（LIS）。

用“牌堆法 + 二分”维护 tails，tails[i] 表示长度为 i+1 的 LIS 末尾最小体重。

复杂度分析：

时间复杂度：O(n log n)，其中 n 为人数。

空间复杂度：O(n)，用于 tails 数组。

class Solution {
    public int bestSeqAtIndex(int[] height, int[] weight) {
        int n = height.length;
        int[][] people = new int[n][2];

        for (int i = 0; i < n; i++) {
            people[i][0] = height[i];
            people[i][1] = weight[i];
        }

        Arrays.sort(people, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            }
            return b[1] - a[1];
        });

        int[] tails = new int[n];
        int size = 0;

        for (int[] person : people) {
            int w = person[1];
            int idx = Arrays.binarySearch(tails, 0, size, w);
            if (idx < 0) {
                idx = -idx - 1;
            }
            tails[idx] = w;
            if (idx == size) {
                size++;
            }
        }

        return size;
    }
}

import "sort"

func bestSeqAtIndex(height []int, weight []int) int {
	people := make([][2]int, len(height))
	for i := 0; i < len(height); i++ {
		people[i] = [2]int{height[i], weight[i]}
	}

	sort.Slice(people, func(i, j int) bool {
		if people[i][0] != people[j][0] {
			return people[i][0] < people[j][0]
		}
		return people[i][1] > people[j][1]
	})

	tails := make([]int, 0, len(people))
	for _, p := range people {
		w := p[1]
		idx := sort.Search(len(tails), func(i int) bool {
			return tails[i] >= w
		})
		if idx == len(tails) {
			tails = append(tails, w)
		} else {
			tails[idx] = w
		}
	}

	return len(tails)
}

相似题目

题目	难度	考察点
300. 最长递增子序列	中等	动态规划 + 二分
354. 俄罗斯套娃信封问题	困难	排序 + LIS
646. 最长数对链	中等	排序 + LIS
673. 最长递增子序列的个数	中等	动态规划
1626. 无矛盾的最佳球队	中等	排序 + 动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/63470513