余晖落尽暮晚霞,黄昏迟暮远山寻
本站
当前位置:网站首页 > 编程知识 > 正文

leetcode1855_go_下标对中的最大距离

xiyangw 2023-09-26 14:10 31 浏览 0 评论

题目

给你两个 非递增 的整数数组 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] 成立,那么该数组是一个 非递增 数组。

示例 1:输入:nums1 = [55,30,5,4,2], nums2 = [100,20,10,10,5] 输出:2

解释:有效下标对是 (0,0), (2,2), (2,3), (2,4), (3,3), (3,4) 和 (4,4) 。

最大距离是 2 ,对应下标对 (2,4) 。

示例 2:输入:nums1 = [2,2,2], nums2 = [10,10,1] 输出:1

解释:有效下标对是 (0,0), (0,1) 和 (1,1) 。

最大距离是 1 ,对应下标对 (0,1) 。

示例 3:输入:nums1 = [30,29,19,5], nums2 = [25,25,25,25,25] 输出:2

解释:有效下标对是 (2,2), (2,3), (2,4), (3,3) 和 (3,4) 。

最大距离是 2 ,对应下标对 (2,4) 。

示例 4:输入:nums1 = [5,4], nums2 = [3,2] 输出:0

解释:不存在有效下标对,所以返回 0 。

提示:1 <= nums1.length <= 105

1 <= nums2.length <= 105

1 <= nums1[i], nums2[j] <= 105

nums1 和 nums2 都是 非递增 数组

解题思路分析

1、双指针;时间复杂度O(n),空间复杂度O(1)

func maxDistance(nums1 []int, nums2 []int) int {
   res := 0
   i := 0
   for j := 0; j < len(nums2); j++ {
      for i < len(nums1) && nums2[j] < nums1[i] {
         i++
      }
      if i < len(nums1) {
         if j-i > res {
            res = j - i
         }
      }
   }
   return res
}

2、二分查找;时间复杂度O(nlog(n)),空间复杂度O(1)

func maxDistance(nums1 []int, nums2 []int) int {
   res := 0
   for j := 0; j < len(nums2); j++ {
      n := min(j, len(nums1))
      i := sort.Search(n, func(i int) bool {
         return nums1[i] <= nums2[j]
      })
      if i < n {
         if j-i > res {
            res = j - i
         }
      }
   }
   return res
}

func min(a, b int) int {
   if a > b {
      return b
   }
   return a
}

3、双指针;时间复杂度O(n),空间复杂度O(1)

func maxDistance(nums1 []int, nums2 []int) int {
   res := 0
   j := 0
   for i := 0; i < len(nums1); i++ {
      for j < len(nums2) && nums1[i] <= nums2[j] {
         j++
      }
      if j-i-1 > res {
         res = j - i - 1
      }
   }
   return res
}

总结

Medium题目,使用双指针

相关推荐

“三次握手,四次挥手”你真的懂吗?

记得刚毕业找工作面试的时候,经常会被问到:你知道“3次握手,4次挥手”吗?这时候我会“胸有成竹”地“背诵”前期准备好的“答案”,第一次怎么怎么,第二次……答完就没有下文了,面试官貌似也没有深入下去的意...

面试官问:三次握手与四次挥手是怎么完成的?

作者|饶全成来源|码农桃花源记得刚毕业找工作面试的时候,经常会被问到:你知道“3次握手,4次挥手”吗?这时候我会“胸有成竹”地“背诵”前期准备好的“答案”,第一次怎么怎么,第二次……答完就没有...

三次握手和四次挥手的高阶面试题,建议收藏

昨天村长的讲解,真是一语点醒,这样的解释胜过死记硬背。但对于学习者,如果不能有直观感受,可能还是觉得不接地气,今天介绍两个工具,一个是网络抓包工具Wireshark,一个是linux命令tcpdum...

三次握手和四次挥手到底是个什么鬼东西

之前总有是有面试官喜欢问,你知道什么是三次握手么?什么是四次挥手么?为什么握手需要三次,挥手需要四次呢?今天我们就来详细的聊一下这个。1.什么是TCPTCP协议,简单称呼一下的话,那就是传输控制协议,...

加深理解TCP的三次握手与四次挥手

在了解三次握手和四次挥手之前,先要知道TCP报文内部包含了那些东西。熟悉了解TCP报文对日后学习网络和排除方面有很大的帮助,所以,今天为了加深对三次握手的理解,从新去认识TCP报文格式。TCP报文格式...

三次握手 与 四次挥手_三次握手四次挥手大白话

三次握手:①首先Client端发送连接请求报文②Server段接受连接后回复ACK报文,并为这次连接分配资源。③Client端接收到ACK报文后也向Server段发生ACK报文...

动画讲解TCP的3次握手,4次挥手,让你一次看明白

专注于Java领域优质技术,欢迎关注作者:老钱占小狼博客TCP三次握手和四次挥手的问题在面试中是最为常见的考点之一。很多读者都知道三次和四次,但是如果问深入一点,他们往往都无法作出准确回答。本篇尝试...

linux下实现免密传输文件或登录到其他服务器

使用scp传输文件到其他服务器的时候,提示需要输密码,如下:[root@18csetup]#scpLINUX.X64_180000_db_home.zip192.168.133.120:/u0...

Linux如何通过salt免密SCP传输上百台机的脚本?看chatGPT的回答

如何通过salt免密SCP传输上百台机的shell脚本”,下面是chatGPT给出的结果。scp批量免密脚本给出的详细shell脚本如下:#!/bin/bash#源文件路径和目标路径SRC_...

Linux/Mac scp命令上传文件_将hdfs上的文件下载到本地的命令是

语法scp[可选参数]file_sourcefile_target参数说明:-1:强制scp命令使用协议ssh1-2:强制scp命令使用协议ssh2-4:强制scp命令只使用IPv4寻...

Linux常用功能——文件远程传输_linux 远程传输文件

scp是securecopy的简写,是linux系统下基于ssh登陆进行安全的远程文件拷贝命令,用于在Linux下进行远程拷贝文件的命令。和它类似的命令有cp,不过cp只是在本机进行拷贝不能跨服务器...

使用 scp 命令定时拉取服务器备份文件

我们的服务器,每周五必须要做下备份,但总是忘记执行备份这件事情,或者是服务器备份做了,但没有做异地备份。所以通过定时任务自动备份,备份成功之后,在其它服务器上面通过定时任务scp命令自动拉取备份文...

windows下最轻便的FTP/SCP文件管理器

这次推荐的工具叫做winscp,这个工具如果是IT从业人员,又是做服务端相关工作的话,可能无人不知,如果是刚入门,推荐立马上手试试。如果看了觉得有用,欢迎收藏、点赞、关注。官方网站:https://w...

我不是网管 - Linux中使用SCP命令安全复制文件

SCP是linux发行版中的命令行工具,用于通过网络安全地跨系统复制文件和目录。SCP代表安全复制,因为它使用ssh协议复制文件。拷贝时,scp命令建立ssh连接到远程系统。换句话说...

WinSCP软件双系统(Win-Linux)文件传输教程

WinSCP软件是windows下的一款使用ssh协议的开源图形化SFTP客户端,也就是一个文件传输的软件,它有什么优点吗,咱们嵌入式开发中经常会将windows中的文件复制到linux系统当中,比较...

取消回复欢迎 发表评论: