This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details
Topic describes
This is the 354. Matryoshka envelope problem on LeetCode.
Tag: “dichotomy”, “sequence DP”
You are given a two-dimensional integer array envelopes, where envelopes[I] = [wi, hi] represents the width and height of the i-th envelope.
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).
Note: Rotating the envelope is not allowed.
Example 1:
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 codeExample 2:
Input: envelopes = [[1,1],[1,1]] Output: 1Copy the codeTip:
- 1 <= envelopes.length <= 5000
- envelopes[i].length == 2
- 1 <= wi, hi <=
Dynamic programming
This is a classic DP model title: Longest ascending subsequence (LIS).
First we sort envelopes to make sure the envelopes are sorted from small to large.
The problem is that we select k envelopes from this sequence to form a new sequence, so that each envelope in the new sequence can strictly cover the previous envelope (width and height are strictly greater than).
We can define state f[I] as the maximum value that takes into account the first I items and ends with the ith item.
For each f[I], the minimum value is 1, which means that you select only one envelope.
So how do I solve for f[I] in general? Because item I has to be selected. We can enumerate the i-1 items in front, which can be the item before the i-1 item.
We update f[I] with Max (f[I], f[j] + 1) as long as any of the pre-i-1 items are eligible.
And then taking a Max in all of them is the answer.
class Solution {
public int maxEnvelopes(int[][] es) {
int n = es.length;
if (n == 0) return n;
// It doesn't matter whether the second dimension (height) is sorted or not, because we iterate through all the i-1 items before the i-1 item
Arrays.sort(es, (a, b)->a[0]-b[0]);
int[] f = new int[n]; // f(I) is the maximum value that takes into account the first I items and ends with the ith item
int ans = 1;
for (int i = 0; i < n; i++) {
// For each f[I], the minimum value is 1
f[i] = 1;
// enumerate the item before the I item,
for (int j = i - 1; j >= 0; j--) {
// Update f[I] with f[j] + 1 as long as there is a previous item that meets the condition
if (check(es, j, i)) {
f[i] = Math.max(f[i], f[j] + 1); }}// select Max as ans in all f[I]
ans = Math.max(ans, f[i]);
}
return ans;
}
boolean check(int[][] es, int mid, int i) {
return es[mid][0] < es[i][0] && es[mid][1] < es[i][1]; }}Copy the code- O(n2)O(n^2)O(n2)
- Space complexity: O(n)O(n)O(n)
Binary + dynamic programming
In fact, the above scheme is a naive one, and the complexity is O(n2)O(n^2)O(n2), which is the first idea I thought of, but the problem does not give the data range, and I do not know whether it can pass.
M: Yes, it’s Hard tag! M: Yes, it’s Hard tag
Now let’s talk about other optimization solutions.
First, as before, we can use complexity analysis to figure out the direction of optimization.
Exponential algorithm optimization down is either logarithmic or linear.
A closer look at the naive solution shows that the optimization is mainly the process of finding the item before the ith item.
If we want to speed up the lookup process, we need to use some kind of data structure for recording.
And update the contents of the data structure as we iterate.
First of all, because we sorted W (from small to large), and the iteration was also carried out from front to back, we only needed to ensure that the same data of W was not updated during the iteration, so that only envelopes meeting the condition of W would appear in G.
At this point, there are two things we need to do: one is h, because we can only join the ascending sequence if both w and H satisfy; One is the length of the ascending sequence corresponding to the envelope, which is the core of our accelerated search.
We use the array G to record, where g[I] represents the minimum “envelope height” in the longest ascending subsequence of length I, and len is required to record the maximum length currently recorded.
Still don’t understand? It doesn’t matter. I must have expressed it badly. We can look at the code directly, I have written the basic logic in the comments (your focus should fall on understanding the g[] array) :
class Solution {
public int maxEnvelopes(int[][] es) {
int n = es.length;
if (n == 0) return n;
// Since we use g to record height, we just need to change w from small to sort
Arrays.sort(es, (a, b)->a[0] - b[0]);
// f(I) is the maximum value that takes into account the first I items and ends with the ith item
int[] f = new int[n];
// g(I) records the minimum envelope height of the longest ascending subsequence of length I
int[] g = new int[n];
// Because you want to take min, use a high enough (impossible) height to initialize
Arrays.fill(g, Integer.MAX_VALUE);
g[0] = 0;
int ans = 1;
for (int i = 0, j = 0, len = 1; i < n; i++) {
// Do not update g array for w identical data
if (es[i][0] != es[j][0]) {
// restrict j from going beyond I to make sure that only the "historical envelope" before the ith envelope appears in g array
while (j < i) {
int prev = f[j], cur = es[j][1];
if (prev == len) {
// Add one more bit to the ascending sequence
g[len++] = cur;
} else {
// Always keep the minimum "envelope height" to ensure that more envelopes can rise with their travel sequence
// For example, keep the minimum height of the sequence 5 (instead of keeping arbitrary ones, such as 10), so that subsequent envelopes 7, 8, 9 can form the sequence;g[prev] = Math.min(g[prev], cur); } j++; }}// Binary process
// g[I] represents the "minimum envelope height" of the ascending subsequence of length I
int l = 0, r = len;
while (l < r) {
int mid = l + r >> 1;
// set check to es[I][1] <= g[mid]
// Find the data nearest the center of the array that meets the check condition.
// find the maximum ascending length of w and h that satisfy the condition
if (es[i][1] <= g[mid]) {
r = mid;
} else {
l = mid + 1; }}// Update f[I] with the answer
f[i] = r;
ans = Math.max(ans, f[i]);
}
returnans; }}Copy the code- Time complexity: For each item there is a “dichotomy” to find the previous item. The complexity is O(nlogn)O(n\log{n})O(nlogn)
- Space complexity: O(n)O(n)O(n)
prove
We can do this assuming that the g-array is dichotomous, which can be achieved by proving that it is “monotonic”.
Of course, this refers to the part where G is used, i.e. [0, len-1].
Let’s review our definition of g[] : g[I] represents the minimum “envelope height” in the longest ascending subsequence of length I
For example, g[] = [0, 3, 4, 5] represents:
- The minimum historical envelope height for ascending sequence length 0 is 0
- The minimum historical envelope height for ascending sequence length 1 is 3
- The minimum historical envelope height for ascending sequence length 2 is 4
- The minimum historical envelope height for ascending sequence length 3 is 5
The monotonicity can be proved by contradiction:
If g[] is not monotonic, that is, at least g[I] > g[j] (I < j, let a = g[I], b = g[j])
It clearly conflicts with our processing logic. Because if you take an envelope of minimum height B and you can make an ascent sequence of length J, you can make an ascent sequence shorter than j, right?
An 🌰, we have the envelope: [[1, 1], [2], [3, 3], [4], [5, 5]], we can make the many kinds of rising of length 2 sequence scheme, which is the smallest solutions are highly the smallest in the [[1, 1], [2]]. Therefore, g[2] = 2, which means that the minimum height of the envelope necessary to make an ascending sequence of length 2 is 2.
In this case, if [2,2] can be used to make an ascending sequence of length 2, it must also be possible to make an ascending sequence of length 1 (delete the other envelopes in front of it).
And by extension, if we have g[j] = b, that means that the degree of growth is zerojThe minimum envelope height required is B. So I must be able to keep the envelopes of height B, delete some of the envelopes in the ascending sequence, and make up an arbitrary length ratiojLittle ascending sequence.
In summary, g[I] > g[j] (I < j) conflicts with processing logic, g[] array is strictly monotone ascending array.
Since g[] is monotonic, we can find the maximum subscript that meets the check condition by “dichotomy” (the maximum subscript reaching the standard indicates the longest ascending sequence length).
Tree array + dynamic programming
In the solution of “dichotomy + dynamic programming”, we optimize the process of finding the i-th file by “dichotomy”.
This process can also be achieved through “tree arrays”.
We still sort w first, and then use a “tree array” to maintain the maximum number of prefixes for the H dimension.
As for the height of H, we only care about the size relationship between multiple envelopes, not the specific difference. We need to discretize H.
In general, if you’re using a tree array, you’re going to have to discretize it, especially if you’re going to use O(n)O(n)O(n) to store dp.
class Solution {
int[] tree;
int lowbit(int x) {
return x & -x;
}
public int maxEnvelopes(int[][] es) {
int n = es.length;
if (n == 0) return n;
// Since we use g to record height, we just need to change w from small to sort
Arrays.sort(es, (a, b)->a[0] - b[0]);
// Discretize all h's first
Set<Integer> set = new HashSet<>();
for (int i = 0; i < n; i++) set.add(es[i][1]);
int cnt = set.size();
int[] hs = new int[cnt];
int idx = 0;
for (int i : set) hs[idx++] = i;
Arrays.sort(hs);
for (int i = 0; i < n; i++) es[i][1] = Arrays.binarySearch(hs, es[i][1]) + 1;
// Create a tree array
tree = new int[cnt + 1];
// f(I) is the maximum value that takes into account the first I items and ends with the ith item
int[] f = new int[n];
int ans = 1;
for (int i = 0, j = 0; i < n; i++) {
// Do not update the tree array for w identical data
if (es[i][0] != es[j][0]) {
// restrict j from crossing I, make sure that only the "historical envelope" before the i-th envelope appears in the tree array.
while (j < i) {
for (int u = es[j][1]; u <= cnt; u += lowbit(u)) {
tree[u] = Math.max(tree[u], f[j]);
}
j++;
}
}
f[i] = 1;
for (int u = es[i][1] - 1; u > 0; u -= lowbit(u)) {
f[i] = Math.max(f[i], tree[u] + 1);
}
ans = Math.max(ans, f[i]);
}
returnans; }}Copy the code- Time complexity: Updating the “tree array” for each item is O(logn)O(\log{n})O(logn). The overall complexity is O(nlogn)O(n\log{n})O(nlogn)
- Space complexity: O(n)O(n)O(n)
The last
This is the No.354 article in our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode by the start date, some of which have locks.
In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.
In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .
In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.