This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

First, the topic overview

LeetCode 354.Russian nesting envelope problem

Given some envelopes marked with width and height, the width and height appear as integer pairs (w, h). When the width and height of another envelope are larger than this one, this envelope can be put into another envelope, like a Russian nesting doll.

Please calculate the maximum number of envelopes that can make up a group of matryoshka envelopes (i.e. one envelope can be placed inside another envelope).

Instructions: Rotating the envelope is not allowed.

Example: input: envelopes = [[5, 4], [6, 4], [6, 7], [2, 3]] output: 3: most of the envelope number 3, combination is: [2, 3] = > [5, 4] = > [6, 7].Copy the code


Interpreting the topic:

In fact, the envelope nesting problem is the longest increasing subsequence problem. When the problem is raised to two dimensions, its solution needs to be sorted according to specific rules, then transformed into a one-dimensional longest increasing subsequence problem, and finally solved by the techniques in the binary search framework.

LIS is the LOngest Incresing Subsequence (LIS).

Each legal nesting is large and small, which is equivalent to finding the longest increasing subsequence whose length is the maximum number of envelopes that can be nested.

A direct idea is to calculate the area by w * H, and then perform the standard LIS algorithm on the area. However, if you think about it a little bit, you can see that this doesn’t work. For example, 1 * 10 is greater than 3 * 3, but obviously these two envelopes can’t be nested into each other.





Second, the idea of implementation

Steps:

  1. The width of the firstwPerform ascending sort if encounteredwThe same case, according to the heighthDescending sort.
  2. And then all of themhAs an array, evaluated on this arrayLISThe length of theta is the answer.

Step 1, as shown in the figure:

Step 2, as shown in the figure:

public class LeetCode_354 {

    / / Time: O (n * log (n)), Space: O (n), Faster - : 87.03%
    public int maxEnvelopes(int[][] envelopes) {

        int n = envelopes.length;
        // In ascending order by width, or descending order by height if the width is the same
        Arrays.sort(envelopes, (a, b) -> a[0] == b[0]? b[1] - a[1] : a[0] - b[0]);

        // Find LIS for the height array
        int [] height = new int[n];
        for (int i = 0; i < n; ++i) {
            height[i] = envelopes[i][1];
        }

        return lengthOfLISBinarySearch(height);
    }

    / / Time: o (n * log (n)), Space: o (n), Faster - : 92.62%
    private int lengthOfLISBinarySearch(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        // The deck count is initialized to 0
        int len = 0;
        int [] top = new int[nums.length];
        for (int x : nums) {
            int left = binarySearchInsertPosition(top, len, x);
            // Put this card on top of the pile
            top[left] = x;
            // Create a new deck if no suitable deck is found
            if (left == len) ++len;
        }
        return len;
    }

    private int binarySearchInsertPosition(int[] d, int len, int x) {
        int low = 0, high = len - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (x < d[mid]) high = mid - 1;
            else if (x > d[mid]) low = mid + 1;
            else return mid;
        }
        returnlow; }}Copy the code

Conclusion:

In fact, this kind of problem can also be extended to three dimensions, such as nested boxes, each box has three dimensions of length, width and height, please calculate the maximum number of boxes can be nested?

According to the previous thinking, it may be thought that: first, the first two dimensions (length and width) are nested in a nested sequence according to the idea of envelope nesting, and finally, LIS is found in the third dimension (height) of the sequence, and the answer can be worked out.

In fact, this line of thinking is wrong. This kind of problem is called “partial ordering problem”, and scaling up to three dimensions makes it much harder, requiring the use of a high-level data structure called a tree array.