当前位置:网站首页>LeetCode_单调栈_中等_456.132 模式
LeetCode_单调栈_中等_456.132 模式
2022-08-09 11:20:00 【小城老街】
1.题目
给你一个整数数组 nums ,数组中共有 n 个整数。132 模式的子序列由三个整数 nums[i]、nums[j] 和 nums[k] 组成,并同时满足:i < j < k 和 nums[i] < nums[k] < nums[j] 。
如果 nums 中存在 132 模式的子序列 ,返回 true ;否则,返回 false 。
示例 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 <= 2 * 105
-109 <= nums[i] <= 109
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/132-pattern
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2.思路
(1)暴力穷举法
该方法比较容易想到,即穷举所有的子序列 [nums[i], nums[j], nums[k]] (i < j < k),如果存在满足 nums[i] < nums[k] < nums[j] 的子序列,则直接返回 true。如果穷举结束之后仍未找到,则说明数组 nums 中不存在 132 模式的子序列,返回 false 即可。需要注意的是,该方法的时间复杂度较高,为 O(n3),在 LeetCode 上提交会出现“超出时间限制”的提示!
(2)单调栈
思路参考该 LeetCode 用户题解。
3.代码实现(Java)
//思路1————暴力穷举法
class Solution {
public boolean find132pattern(int[] nums) {
for (int i = 0; i < nums.length - 2; i++) {
for (int j = i + 1; j < nums.length - 1; j++) {
if (nums[i] >= nums[j]) {
continue;
}
for (int k = j + 1; k < nums.length; k++) {
if (nums[i] < nums[k] && nums[k] < nums[j]) {
return true;
}
}
}
}
return false;
}
}
//思路2————单调栈
class Solution {
public boolean find132pattern(int[] nums) {
Stack<Integer> stack = new Stack<>();
int nums_k = Integer.MIN_VALUE;
//从后往前遍历
for (int i = nums.length - 1; i >= 0; i--) {
//由于 nums_k
if (nums[i] < nums_k) {
return true;
}
//维护单调递减栈(栈顶元素最小,栈底元素最大)
while (!stack.isEmpty() && stack.peek() < nums[i]) {
nums_k = Math.max(nums_k, stack.pop());
}
stack.push(nums[i]);
}
return false;
}
}
边栏推荐
猜你喜欢
随机推荐
学长告诉我,大厂MySQL都是通过SSH连接的
TIC2000系列处理器在线升级
CAN总线发送数据
ClickHouse之MaterializeMySQL引擎(十)
激光条纹中心提取——Steger
【DB运营管理/开发解决方案】上海道宁为您提供提高工作便利性的集成开发工具——Orange
未来装备探索:数字孪生装备
PAT1007
_main C:/ti/ccs1011/ccs/tools/compiler/ti-cgt-c2000_20.2.1.LTS/lib/rts2800_fpu32.lib<ar在线升级跳转疑问
API接口是什么?API接口常见的安全问题与安全措施有哪些?
es6Generator函数的异常处理
程序员的专属浪漫——用3D Engine 5分钟实现烟花绽放效果
redis的缓存穿透、缓存雪崩、缓存击穿怎么搞?
排序--快排(图解)
PAT1001
实现strcat函数
ClickHouse物化视图(八)
es6递归函数
预置第三方apk到MTK项目相关问题总结
MySQL传统方案和通过SSH连接哪个好?