详解为何使用「单调栈」来找最大的 K 是正确的|Java 刷题打卡

简介: 详解为何使用「单调栈」来找最大的 K 是正确的|Java 刷题打卡

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


题目描述



这是 LeetCode 上的 456. 132 模式 ,难度为 中等


Tag : 「单调栈」


给你一个整数数组 nums ,数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成,并同时满足:i < j < k 和 nums[i] < nums[k] < nums[j] 。


如果 nums 中存在 132 模式的子序列 ,返回 true ;否则,返回 false 。


进阶:很容易想到时间复杂度为 O(n^2)O(n2) 的解决方案,你可以设计一个时间复杂度为 O(n logn)O(nlogn)O(n)O(n) 的解决方案吗?


示例 1:


输入:nums = [1,2,3,4]
输出:false
解释:序列中不存在 132 模式的子序列。
复制代码


示例 2:


输入:nums = [3,1,4,2]
输出:true
解释:序列中有 1 个 132 模式的子序列: [1, 4, 2] 。
复制代码


示例 3:


输入:nums = [-1,3,2,0]
输出:true
解释:序列中有 3 个 132 模式的的子序列:[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。
复制代码


提示:


  • n == nums.length
  • 1 <= n <= 10^4104
  • -10^9109 <= nums[i] <= 10^9109


基本思路



朴素的做法是分别对三个数进行枚举,这样的做法是 O(n^3)O(n3) 的,数据范围是 10^4104,稳稳超时。


事实上,这样的数据范围甚至不足以我们枚举其中两个数,然后优化找第三个数的 O(n^2)O(n2) 做法。


这时候根据数据范围会联想到树状数组,使用树状数组的复杂度是 O(n\log{n})O(nlogn) 的,可以过。但是代码量会较多一点,还需要理解离散化等前置知识


题解也不太好写。


因此,我们可以从 132 的大小特性去分析,如果在确定一个数之后,如何快速找到另外两个数(我们使用 ijk 来代指 132 结构):


  1. 枚举 i:由于 i 是 132 结构中最小的数,那么相当于我们要从 i 后面,找到一个对数 (j,k),使得 (j,k) 都满足比 i 大,同时 jk 之间存在 j > k 的关系。由于我们的遍历是单向的,因此我们可以将问题转化为找 k,首先 k 需要比 i 大,同时在 [i, k] 之间存在比 k 大的数即可。
  2. 枚举 j:由于 j 是 132 结构里最大的数,因此我们需要在 j 的右边中比 j 小的「最大」的数,在 j 的左边找比 j 小的「最小」的数。这很容易联想到单调栈,但是朴素的单调栈是帮助我们找到左边或者右边「最近」的数,无法直接满足我们「最大」和「最小」的要求,需要引入额外逻辑。
  3. 枚举 k:由于 k 是 132 结构中的中间值,这里的分析逻辑和「枚举 i」类似,因为遍历是单向的,我们需要找到 k 左边的 i,同时确保 [i,k] 之间存在比 ik 大的数字。


以上三种分析方法都是可行的,但「枚举 i」的做法是最简单的。


因为如果存在 (j,k) 满足要求的话,我们只需要找到一个最大的满足条件的 k,通过与 i 的比较即可。


也许你还不理解是什么意思。没关系,我们一边证明一边说。


过程 & 证明



先说处理过程吧,我们从后往前做,维护一个「单调递减」的栈,同时使用 k 记录所有出栈元素的最大值(k 代表满足 132 结构中的 2)。


那么当我们遍历到 i,只要满足发现满足 nums[i] < k,说明我们找到了符合条件的 i j k


举个🌰,对于样例数据 [3, 1, 4, 2],我们知道满足 132 结构的子序列是 [1, 4, 2],其处理逻辑是(遍历从后往前):


  1. 枚举到 2:栈内元素为 [2],k = INF
  2. 枚举到 4:不满足「单调递减」,2 出栈更新 k,4 入栈。栈内元素为 [4],k = 2
  3. 枚举到 1:满足 nums[i] < k,说明对于 i 而言,后面有一个比其大的元素(满足 i < k 的条件),同时这个 k 的来源又是因为维护「单调递减」而弹出导致被更新的(满足 ik 之间,有比 k 要大的元素)。因此我们找到了满足 132 结构的组合。


这样做的本质是:我们通过维护「单调递减」来确保已经找到了有效的 (j,k)。换句话说如果 k 有值的话,那么必然是因为有 j > k,导致的有值。也就是 132 结构中,我们找到了 32,剩下的 i (也就是 132 结构中的 1)则是通过遍历过程中与 k 的比较来找到。这样做的复杂度是 O(n)O(n) 的,比树状数组还要快。


从过程上分析,是没有问题的。


搞清楚了处理过程,证明也变得十分简单。


我们不失一般性的考虑任意数组 nums,假如真实存在 ijk 符合 132 的结构(这里的 ijk 特指所有满足 132 结构要求的组合中 k 最大的那个组合)。


由于我们的比较逻辑只针对 ik,而 i 是从后往前的处理的,必然会被遍历到;漏掉 ijk 的情况只能是:在遍历到 i 的时候,我们没有将 k 更新到变量中:


  1. 这时候变量的值要比真实情况下的 k 要小,说明 k 还在栈中,而遍历位置已经到达了 i,说明 jk 同时在栈中,与「单调递减」的性质冲突。
  2. 这时候变量的值要比真实情况下的 k 要大,说明在 k 出栈之后,有比 k 更大的数值出栈了(同时必然有比变量更大的值在栈中),这时候要么与我们假设 ijkk 最大的组合冲突;要么与我们遍历到的位置为 i 冲突。


综上,由于「单调递减」的性质,我们至少能找到「遍历过程中」所有符合条件的 ijkk 最大的那个组合。


单调栈



代码:


class Solution {
    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        Deque<Integer> d = new ArrayDeque<>();
        int k = Integer.MIN_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            if (nums[i] < k) return true;
            while (!d.isEmpty() && d.peekLast() < nums[i]) {
                // 事实上,k 的变化也具有单调性,直接使用 k = pollLast() 也是可以的
                k = Math.max(k, d.pollLast()); 
            }
            d.addLast(nums[i]);
        }
        return false;
    }
}
复制代码


  • 时间复杂度:O(n)O(n)
  • 空间复杂度:O(n)O(n)


最后



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


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


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


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

相关文章
|
8月前
|
存储 IDE Java
java设置栈内存大小
在Java应用中合理设置栈内存大小是确保程序稳定性和性能的重要措施。通过JVM参数 `-Xss`,可以灵活调整栈内存大小,以适应不同的应用场景。本文介绍了设置栈内存大小的方法、应用场景和注意事项,希望能帮助开发者更好地管理Java应用的内存资源。
388 4
|
10月前
|
存储 算法 Java
Java 内存管理与优化:掌控堆与栈,雕琢高效代码
Java内存管理与优化是提升程序性能的关键。掌握堆与栈的运作机制,学习如何有效管理内存资源,雕琢出更加高效的代码,是每个Java开发者必备的技能。
237 5
|
11月前
|
存储 算法 Java
🧠Java零基础 - Java栈(Stack)详解
【10月更文挑战第17天】本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
384 2
|
12月前
|
存储 安全 Java
【用Java学习数据结构系列】探索栈和队列的无尽秘密
【用Java学习数据结构系列】探索栈和队列的无尽秘密
105 2
|
存储 算法 Java
惊!Java程序员必看:JVM调优揭秘,堆溢出、栈溢出如何巧妙化解?
【8月更文挑战第29天】在Java领域,JVM是代码运行的基础,但需适当调优以发挥最佳性能。本文探讨了JVM中常见的堆溢出和栈溢出问题及其解决方法。堆溢出发生在堆空间不足时,可通过增加堆空间、优化代码及释放对象解决;栈溢出则因递归调用过深或线程过多引起,调整栈大小、优化算法和使用线程池可有效应对。通过合理配置和调优JVM,可确保Java应用稳定高效运行。
361 4
|
Java 索引
java中的栈(利用数组实现栈)
这篇文章通过Java代码示例介绍了如何使用数组实现栈操作,包括栈的初始化、入栈、出栈、判断栈满和空以及遍历栈的方法。
java中的栈(利用数组实现栈)
|
存储 Java 对象存储
Java虚拟机(JVM)中的栈(Stack)和堆(Heap)
在Java虚拟机(JVM)中,栈(Stack)和堆(Heap)是存储数据的两个关键区域。它们在内存管理中扮演着非常重要的角色,但各自的用途和特点有所不同。
166 0
|
Java 运维
开发与运维命令问题之使用jstack命令查看Java进程的线程栈如何解决
开发与运维命令问题之使用jstack命令查看Java进程的线程栈如何解决
156 2
|
存储 Java
JAVA程序运行问题之JVM 中的栈如何解决
JAVA程序运行问题之JVM 中的栈如何解决
|
存储 安全 Java
Java集合篇之逐渐被遗忘的Stack,手写一个栈你会吗?
总之,虽然在日常开发中,`java.util.Stack`正逐渐被其他类如 `Deque`接口的实现所取代,但手写一个栈(无论是基于数组还是链表)都是一次很好的编程练习,它可以帮助开发者更加深入地理解栈这种数据结构的工作原理和各种操作。
105 0

热门文章

最新文章