马戏团人塔

// 题目思路：
// 同样的，我们需要根据身高和体重来构建一个最长递增子序列。
// 使用Java Stream来对数据进行排序，并利用二分查找来寻找LIS。

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class CircusTowerStream {
    public int maxEnvelopes(int[] height, int[] weight) {
        List<int[]> people = Arrays.stream(height)
            .boxed()
            .map(i -> new int[]{height[i], weight[i]})
            .sorted((a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0])
            .collect(Collectors.toList());

        int[] dp = new int[people.size()];
        int maxLength = 0;

        for (int[] person : people) {
            int weightValue = person[1];
            int left = 0, right = maxLength;
            while (left < right) {
                int mid = (left + right) / 2;
                if (dp[mid] < weightValue) left = mid + 1;
                else right = mid;
            }
            dp[left] = weightValue;
            if (left == maxLength) maxLength++;
        }

        return maxLength;
    }

    public static void main(String[] args) {
        CircusTowerStream tower = new CircusTowerStream();
        int[] height = {65, 70, 56, 75, 60, 68};
        int[] weight = {100, 150, 90, 190, 95, 110};
        System.out.println(tower.maxEnvelopes(height, weight));
    }
}