程序员面试金典17.08_go_马戏团人塔题目有个马戏团正在设计叠罗汉的表演节

题目有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。
出于实际和美观的考虑，在上面的人要比下面的人矮一点且轻一点。
已知马戏团每个人的身高和体重，请编写代码计算叠罗汉最多能叠几个人。
示例：输入：height = [65,70,56,75,60,68] weight = [100,150,90,190,95,110] 输出：6
解释：从上往下数，叠罗汉最多能叠 6 层：
(56,90), (60,95),(65,100), (68,110), (70,150), (75,190)
提示： height.length == weight.length <= 10000
解题思路分析1、二分查找；时间复杂度O(nlog(n)) ，空间复杂度O(n)
文章插图
func bestSeqAtIndex(height []int, weight []int) int { arr := make([][2]int, 0) for i := 0; i < len(height); i++ {arr = append(arr, [2]int{height[i], weight[i]}) } sort.Slice(arr, func(i, j int) bool {if arr[i][0] == arr[j][0] {return arr[i][1] < arr[j][1]}return arr[i][0] > arr[j][0] }) res := make([]int, 0) for i := 0; i < len(arr); i++ {if len(res) == 0 || arr[res[len(res)-1]][0] > arr[i][0]i < len(height); i++ {arr = append(arr, [2]int{height[i], weight[i]}) } sort.Slice(arr, func(i, j int) bool {if arr[i][0] == arr[j][0] {return arr[i][1] < arr[j][1]}return arr[i][0] > arr[j][0] }) res := make([]int, 0) for i := 0; i < len(arr); i++ {index := sort.Search(len(res), func(j int) bool {return arr[res[j]][0] <= arr[i][0] || arr[res[j]][1] <= arr[i][1]})if index == len(res) {res = append(res, i)} else {res[index] = i} } return len(res)}总结【程序员面试金典17.08_go_马戏团人塔】Medium题目，题目同Leetcode 354.俄罗斯套娃信封问题，使用动态规划会超时