MaxEnvelopes.js

"use strict";
exports.__esModule = true;
/**
 * 给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
 * 请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
 * @param {number[][]} envelopes
 * @return {number}
 */
function maxEnvelopes(envelopes) {
    if (!Array.isArray(envelopes) || envelopes.length < 1) {
        return 0;
    }
    // 首先对于宽度按升序排序，之后对于相同宽度则按照降序排序，因为两个宽度相同的信封不能相互包含，逆序保证在宽度相同的数对中最多选择一个
    envelopes.sort(function (a, b) { return a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]; });
    // 之后就是一个根据高度寻找最长递增序列的问题
    var height = [];
    // 使用二分查找找到高度中和合适值
    for (var i in envelopes) {
        height[i] = envelopes[i][1];
    }
    return HeightLTS(height);
}
exports.maxEnvelopes = maxEnvelopes;
;
/**
 * 传入一个数组，对这个数组寻找最大连续增大序列的长度。
 * @param  {number[]} height
 * @return {number}
 */
function HeightLTS(height) {
    var count = 0, len = height.length, queue = [];
    for (var i = 0; i < len; i++) {
        var env = height[i];
        var left = 0, right = count;
        // 寻找插入此信封的位置
        while (left < right) {
            var mid = left + Math.floor((right - left) / 2);
            if (queue[mid] >= env) {
                right = mid;
            }
            else {
                left = mid + 1;
            }
        }
        // 增加一个信封
        if (left === count)
            count++;
        // 把这个信封添加到队列
        queue[left] = env;
    }
    return count;
}