当前位置：首页 > news >正文

LeetCode -- Russian Doll Envelopes

news 来源：原创 2024/5/8 23:11:08

题目描述：
You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

Example:
Given envelopes = [[5,4],[6,4],[6,7],[2,3]], the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

给定一个二维数组，对于[i,j]和[a,b]若满足i<a且j<b，则成为Russian doll。统计满足Russian doll的个数。

思路：

1. 使用类建模，对整个数组排序

2. 两层循环，排序后从第一个往后遍历(i:0->n)；内层循环从后向前查找(j:i->0)：
若a[i,0]>a[j,0] && a[0,i] > a[0,j]则取 Max(a[i]当前的结果,a[j]的结果+1)
因此可使用DP，用result[i]来存a[i]的Russian doll的数量，初始化为1。

实现代码：

public int MaxEnvelopes(int[,] envelopes)
    {
        if(envelopes == null || envelopes.Length == 0){
    		return 0;
    	}
    	
    	// 0. model the problem
    	var arr = new List<Doll>();
    	var rowCount = envelopes.Length / 2;
    
    	for (var i = 0;i < rowCount; i++){
    		arr.Add(new Doll(envelopes[i,0], envelopes[i,1]));
    	}
    	
    	// 1. sort the arrays 
    	arr = arr.OrderBy(x=>x).ToList();
    	
    	var result = new int[rowCount];
    	for (var i = 0;i < rowCount; i++){
    		// fetch the item from first to last
    		result[i] = 1;
    		for (var j = i-1;j >=0 ; j--){
    			if(arr[i].Width > arr[j].Width && arr[i].Height > arr[j].Height){
    				result[i] = Math.Max(result[i], result[j]+1);
    			}
    		}
    	}
    	//Console.WriteLine(result);
    	var max = result.Max();
    	
    	return max;
    	
    }
    
    public class Doll : IComparable
    {
    	public int Width;
    	public int Height;
    	public Doll(int width, int height){
    		this.Width = width;
    		this.Height = height;
    	}
    	
    	public int CompareTo(object obj){
    		var to = (Doll)obj;
    		if(Width!=to.Width){
    			return Width - to.Width;
    		}else{
    			return Height - to.Height;
    		}
    	}
    }