缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
进阶：你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？
示例 1：
输入：nums = [1,2,0]
输出：3

示例 2：
输入：nums = [3,4,-1,1]
输出：2

示例 3：
输入：nums = [7,8,9,11,12]
输出：1

提示：

0 <= nums.length <= 300
-231 <= nums[i] <= 231 - 1

以下程序实现了这一功能，请你填补空白处内容：

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        int contains = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                contains++;
                break;
            }
        }
        if (contains == 0) {
            return 1;
        }
        for (int i = 0; i < n; i++) {
            _________________;
        }
        for (int i = 0; i < n; i++) {
            int a = Math.abs(nums[i]);
            nums[a - 1] = -Math.abs(nums[a - 1]);
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }
}

Java解答参考

  if ((nums[i] <= 0) || (nums[i] > n)) {
    nums[i] = 1;
}

俄罗斯套娃信封问题

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。
示例 1：

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为
3, 组合为:
[2,3] => [5,4] => [6,7]。

示例 2：

输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1

提示：

1 <= envelopes.length <= 5000
envelopes[i].length == 2
1 <= wi, hi <= 104

Java解答参考

 class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        if (n == 0)
            return 0;
        Arrays.sort(envelopes, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                if (a[0] != b[0])
                    return a[0] - b[0];
                return b[1] - a[1];
            }
        });
        List<Integer> lastHeight = new ArrayList<>();
        lastHeight.add(envelopes[0][1]);
        for (int i = 1; i < n; i++) {
            int h = envelopes[i][1];
            if (h > lastHeight.get(lastHeight.size() - 1))
                lastHeight.add(h);
            else {
                int l = 0, r = lastHeight.size() - 1;
                while (r > l) {
                    int m = (l + r) >> 1;
                    if (lastHeight.get(m) < h)
                        l = m + 1;
                    else
                        r = m;
                }
                lastHeight.set(l, h);
            }
        }
        return lastHeight.size();
    }
}