1855. 下标对中的最大距离 力扣

题目描述给你两个非递增的整数数组nums1​​​​​​ 和nums2​​​​​​ 数组下标均从 0 开始计数。下标对(i, j)中0 i nums1.length且0 j nums2.length。如果该下标对同时满足i j且nums1[i] nums2[j]则称之为有效下标对该下标对的距离为j - i​​ 。​​返回所有有效下标对(i, j)中的最大距离。如果不存在有效下标对返回0。一个数组arr如果每个1 i arr.length均有arr[i-1] arr[i]成立那么该数组是一个非递增数组。题目链接1855. 下标对中的最大距离 - 力扣LeetCode解题思路1. 暴力两个循环遍历两个数组超时于是剪枝2. 第一个剪枝当 num2 的长度 - 当前 num1 的下标 当前最大距离时则直接退出第一个循环返回结果。因为即使是 num2 的最后一位比当前的 num1 元素大下标相差的数值也不能超过当前记录的最大距离。3. 第二个剪枝当 num1[ i ] num2[ j ] 时则退出第二个循环。因为两个数组都是非递增如果 num1[ i ] num2[ j ]就有num1[ i ] num2[ j ] num2[ j 1 ] num2[ j 2 ] ...4. 优化第二个循环第二个循环直接从第一个循环下标1当前最大距离开始。如果进入第二个循环不能更新最大距离为什么还要进入第二个循环呢...代码如下class Solution { public: int maxDistance(vectorint nums1, vectorint nums2) { int length1 nums1.size(); int length2 nums2.size(); int ans 0; int x; for ( int i 0; i length1; i ){ if ( ans length2 - i ) break; for ( int j i ans 1; j length2; j ){ if ( nums1[ i ] nums2[ j ] ){ ans; }else{ break; } } } return ans; } };