1855. Maximum distance of subscript alignment

Address ：

Power button https://leetcode-cn.com/problems/maximum-distance-between-a-pair-of-values/

subject ：

Here are two for you Non-increasing Array of integers for nums1​​​​​​ and nums2​​​​​​ , Array subscripts are from 0 Start Count .

Subscript pair (i, j) in 0 <= i < nums1.length And 0 <= j < nums2.length . If the subscript pair satisfies both i <= j And nums1[i] <= nums2[j] , Call it It works Subscript pair , The subscript is right distance by j - i​​ .​​

Back to all It works Subscript pair (i, j) Medium Maximum distance . If there is no valid subscript pair , return 0 .

An array arr , If each 1 <= i < arr.length Both arr[i-1] >= arr[i] establish , So the array is a Non-increasing Array .

Example 1：

Input ：nums1 = [55,30,5,4,2], nums2 = [100,20,10,10,5] Output ：2 explain ： The valid subscript pair is (0,0), (2,2), (2,3), (2,4), (3,3), (3,4) and (4,4) . The maximum distance is 2 , Corresponding subscript pair (2,4) .

Example 2：

Input ：nums1 = [2,2,2], nums2 = [10,10,1] Output ：1 explain ： The valid subscript pair is (0,0), (0,1) and (1,1) . The maximum distance is 1 , Corresponding subscript pair (0,1) .

Example 3：

Input ：nums1 = [30,29,19,5], nums2 = [25,25,25,25,25] Output ：2 explain ： The valid subscript pair is (2,2), (2,3), (2,4), (3,3) and (3,4) . The maximum distance is 2 , Corresponding subscript pair (2,4) .

Example 4：

Input ：nums1 = [5,4], nums2 = [3,2] Output ：0 explain ： There is no valid subscript pair , So back 0 .

Tips ：

1 <= nums1.length <= 105 1 <= nums2.length <= 105 1 <= nums1[i], nums2[j] <= 105 nums1 and nums2 All are Non-increasing Array

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/maximum-distance-between-a-pair-of-values
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas ：

For a non increasing array , It means that the value of array elements is decreasing

Traverse the array according to the meaning of the question 1 Every element of , And array 2 Compare the elements of , Find the maximum distance

To reduce the number of comparisons , From the array 2 Compare the last element of , This is the longest distance , If it doesn't , Then compare the second

Such a violent solution is bound to timeout , The code is posted below

Since violence doesn't work, we have to think of other ways

Because it is a comparative distance , Array values are not directly related to distance , Therefore, two sets of data cannot be deduced , We can only compare

With i As Array 1 The subscript ,j As Array 2 The subscript

i from 0 Start , Initially found step （ Longest distance ） zero

[i] In the array 2 Look for the biggest place to exist , The last one [i] <= [j], Set up step = j - i

first i When the element is complete , We found the step size

The next element i+1 The element benchmarking is j+1 The location of ,

         There may be [i+1] == [j+1] , A distance of 0, It won't be longer than the last time , So don't consider

         May also be [i+1] <= [j+n],j After a certain step n In the back . This address is where we start to compare , therefore

        The step length we found in the first step is used as a new starting point , If a new starting point [j] > [i], We will continue to try j Move back to find a new step

Such a calculation step can effectively reduce the number of comparisons

Method 1 、BF

int maxDistance(int* nums1, int nums1Size, int* nums2, int nums2Size){
	int i, j;
	int max = 0;
	
	for(i=0; i<nums1Size; i++)
	{
		for(j=nums2Size-1; j>=0; j--)
		{
			if(nums1[i] <= nums2[j])
			{
				if(max < (j-i) )
					max = j-i;
				
				break;
			}
		}
	}
	
	return max;
}

Method 2 、 Step comparison

int maxDistance(int* nums1, int nums1Size, int* nums2, int nums2Size){
	int i, j;
	int step = 0;
	
	for(i=0; i<nums1Size; i++)
	{
		if(i+step < nums2Size && nums1[i] > nums2[i+step])
			continue;
			
		for(j=i+step; j<nums2Size; j++)
		{
			//printf("2..nums1[%d]=%d, nums2[%d]=%d\n", i, nums1[i], j, nums2[j]);
			if(nums1[i] <= nums2[j])
			{
				step = j-i;
			}
			else
				break;
		}	
	}
	
	return step;
}

See more brush notes