【综合笔试题】根据答案具有「二段性」进行二分滑动窗口求解|Java 刷题打卡

简介: 【综合笔试题】根据答案具有「二段性」进行二分滑动窗口求解|Java 刷题打卡

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的1438. 绝对差不超过限制的最长连续子数组,难度为 Medium


给你一个整数数组 nums ,和一个表示限制的整数 limit,请你返回最长连续子数组的长度,该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。


如果不存在满足条件的子数组,则返回 0 。


示例 1:


输入:nums = [8,2,4,7], limit = 4
输出:2 
解释:所有子数组如下:
[8] 最大绝对差 |8-8| = 0 <= 4.
[8,2] 最大绝对差 |8-2| = 6 > 4. 
[8,2,4] 最大绝对差 |8-2| = 6 > 4.
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
[2] 最大绝对差 |2-2| = 0 <= 4.
[2,4] 最大绝对差 |2-4| = 2 <= 4.
[2,4,7] 最大绝对差 |2-7| = 5 > 4.
[4] 最大绝对差 |4-4| = 0 <= 4.
[4,7] 最大绝对差 |4-7| = 3 <= 4.
[7] 最大绝对差 |7-7| = 0 <= 4. 
因此,满足题意的最长子数组的长度为 2 。
复制代码


示例 2:


输入:nums = [10,1,2,4,7,2], limit = 5
输出:4 
解释:满足题意的最长子数组是 [2,4,7,2],其最大绝对差 |2-7| = 5 <= 5 。
复制代码


示例 3:


输入:nums = [4,2,2,2,4,4,2,2], limit = 0
输出:3
复制代码


提示:


  • 1 <= nums.length <= 10^5105
  • 1 <= nums[i] <= 10^9109
  • 0 <= limit <= 10^9109


二分 + 滑动窗口



数据范围是 10^5105,因此只能考虑「对数解法」和「线性解法」。


对数解法很容易想到「二分」。


在给定 limit 的情况下,倘若有「恰好」满足条件的区间长度为 len,必然存在满足条件且长度小于等于 len 的区间,同时必然不存在长度大于 len 且满足条件的区间。


因此长度 len 在数轴中具有「二段性」。


问题转化为「如何判断 nums 中是否有长度 len 的区间满足绝对值不超过 limit


我们可以枚举区间的右端点 r,那么对应的左端点为 r - len + 1,然后使用「单调队列」来保存区间的最大值和最小值。


class Solution {
    public int longestSubarray(int[] nums, int limit) {
        int n = nums.length;
        int l = 1, r = n;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (check(nums, mid, limit)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return r;
    }
    boolean check(int[] nums, int len, int limit) {
        int n = nums.length;
        Deque<Integer> max = new ArrayDeque<>(), min = new ArrayDeque<>();
        for (int r = 0, l = r - len + 1; r < n; r++, l = r - len + 1) {
            if (!max.isEmpty() && max.peekFirst() < l) {
                max.pollFirst();
            }
            while (!max.isEmpty() && nums[r] >= nums[max.peekLast()]) {
                max.pollLast();
            }
            max.addLast(r);
            if (!min.isEmpty() && min.peekFirst() < l) {
                min.pollFirst();
            }
            while (!min.isEmpty() && nums[r] <= nums[min.peekLast()]) {
                min.pollLast();
            }
            min.addLast(r);
            if (l >= 0 && Math.abs(nums[max.peekFirst()] - nums[min.peekFirst()]) <= limit) {
                return true;
            }
        }
        return false;
    }
}
复制代码


  • 时间复杂度:枚举长度的复杂度为 O(\log{n})O(logn),对于每次 check 而言,每个元素最多入队和出队常数次,复杂度为 O(n)O(n)。整体复杂度为 O(n\log{n})O(nlogn)
  • 空间复杂度:O(n)O(n)


双指针



上述解法我们是在对 len 进行二分,而事实上我们可以直接使用「双指针」解法找到最大值。


始终让右端点 r 右移,当不满足条件时让 l 进行右移。


同时,还是使用「单调队列」保存我们的区间最值,这样我们只需要对数组进行一次扫描即可得到答案。


class Solution {
    public int longestSubarray(int[] nums, int limit) {
        int n = nums.length;
        int ans = 0;
        Deque<Integer> max = new ArrayDeque<>(), min = new ArrayDeque<>();
        for (int r = 0, l = 0; r < n; r++) {
            while (!max.isEmpty() && nums[r] >= nums[max.peekLast()]) {
                max.pollLast();
            }
            max.addLast(r);
            while (!min.isEmpty() && nums[r] <= nums[min.peekLast()]) {
                min.pollLast();
            }
            min.addLast(r);
            while (Math.abs(nums[max.peekFirst()] - nums[min.peekFirst()]) > limit) {
                l++;
                if (max.peekFirst() < l) max.pollFirst();
                if (min.peekFirst() < l) min.pollFirst();
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}
复制代码


  • 时间复杂度:每个元素最多入队和出队常数次,复杂度为 O(n)O(n)
  • 空间复杂度:O(n)O(n)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.1438 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
4月前
|
搜索推荐 算法 Java
2025 年互联网大厂校园招聘 JAVA 工程师笔试题及备考要点解析
本文针对互联网大厂校招Java工程师笔试题进行解析,涵盖基础知识、面向对象编程、数据结构与算法、异常处理及集合框架等核心内容。从数据类型、运算符到流程控制语句,从类与对象、继承多态到数组链表、排序算法,再到异常捕获与集合框架应用,结合实际案例深入剖析,助你系统掌握考点,提升应试能力。资源链接:[点此获取](https://pan.quark.cn/s/14fcf913bae6)。
168 9
|
4月前
|
Java 数据库连接 API
互联网大厂校招 JAVA 工程师笔试题解析及常见考点分析
本文深入解析互联网大厂校招Java工程师笔试题,涵盖基础知识(数据类型、流程控制)、面向对象编程(类与对象、继承与多态)、数据结构与算法(数组、链表、排序算法)、异常处理、集合框架、Java 8+新特性(Lambda表达式、Stream API)、多线程与并发、IO与NIO、数据库操作(JDBC、ORM框架MyBatis)及Spring框架基础(IoC、DI、AOP)。通过技术方案讲解与实例演示,助你掌握核心考点,提升解题能力。
176 2
|
4月前
|
设计模式 算法 Java
2025 春季校招 Java 研发笔试题详细解析及高效学习指南
本指南专为2025春季校招Java研发岗位笔试设计,涵盖Java 17+新特性(如模式匹配、文本块、记录类和密封类)、现代技术栈(Spring Boot 3、响应式编程、Stream API增强)以及算法与数据结构实战。同时深入解析Spring Data JPA、事务管理、性能优化等内容,并结合实际案例讲解常见算法题解与设计模式应用。资源包含核心知识点、面试题及笔试技巧,助力高效备考。下载地址:[链接](https://pan.quark.cn/s/14fcf913bae6)。
93 1
|
4月前
|
存储 算法 NoSQL
2025 春季校招 java 研发岗位笔试题及相关内容
这份指南针对2025春季校招Java研发岗位,系统梳理了笔试核心知识点。内容涵盖Java基础(关键字、数据类型、循环与条件判断)、集合框架(List、Set、Map)、多线程(创建、同步、休眠与等待)以及异常处理(类型与机制)。通过典型例题解析与实践指导,帮助求职者掌握解题思路,提升编程能力,为成功通过校招笔试奠定基础。资源链接:[https://pan.quark.cn/s/14fcf913bae6](https://pan.quark.cn/s/14fcf913bae6)
144 0
|
12月前
|
消息中间件 Java Kafka
Flink-08 Flink Java 3分钟上手 滑动窗口 SlidingWindow 时间驱动 事件驱动 TimeWindow CountWindow GlobalWindow
Flink-08 Flink Java 3分钟上手 滑动窗口 SlidingWindow 时间驱动 事件驱动 TimeWindow CountWindow GlobalWindow
198 7
|
存储 Java 编译器
刷完一千道java笔试题的常见题目分析
这篇文章是关于刷完一千道Java笔试题后的常见题目分析,涵盖了Java基础知识点,如标识符命名规则、抽象类与接口的区别、String类的equals方法、try-catch-finally块的执行逻辑、类与实例方法的区别、this与super关键字的用法、面向对象的基本概念、重写与重载的原则等,并建议结合JVM内存结构图加深理解。
刷完一千道java笔试题的常见题目分析
|
算法 Java UED
详解 Java 限流接口实现问题之滑动窗口限流算法的缺点如何解决
详解 Java 限流接口实现问题之滑动窗口限流算法的缺点如何解决
292 0
|
Java
2022蓝桥杯大赛软件类省赛Java大学B组真题 刷题统计
2022蓝桥杯大赛软件类省赛Java大学B组真题 刷题统计
164 0
|
Java
JAVA数据结构刷题 -- 二叉树进阶
JAVA数据结构刷题 -- 二叉树进阶
103 0
|
Java
java 常用二分
二分法查找(折半查找) java版本
277 0

热门文章

最新文章