写点什么

【LeetCode】132 模式 Java 题解

用户头像
HQ数字卡
关注
发布于: 2021 年 03 月 24 日

题目

给定一个整数序列:a1, a2, ..., an,一个 132 模式的子序列 ai, aj, ak 被定义为:当 i < j < k 时,ai < ak < aj。设计一个算法,当给定有 n 个数字的序列时,验证这个序列中是否含有 132 模式的子序列。


来源:力扣(LeetCode)


链接:https://leetcode-cn.com/problems/132-pattern


代码


public class DayCode {    public static void main(String[] args) {        int[] nums = new int[]{};        boolean ans = new DayCode().find132pattern(nums);        System.out.println(ans);    }
/** * 题目链接:https://leetcode-cn.com/problems/132-pattern/ * 时间复杂度 O(n) * 空间复杂度 O(n) * * @param nums * @return */ public boolean find132pattern(int[] nums) { boolean ans = false; int n = nums.length; if (n < 3) { return ans; }
int[] minArr = new int[n]; minArr[0] = nums[0]; for (int i = 1; i < n; i++) { minArr[i] = Math.min(minArr[i - 1], nums[i]); }
Stack<Integer> stack = new Stack<>(); for (int i = n - 1; i >= 0; i--) { if (nums[i] > minArr[i]) { while (!stack.isEmpty() && stack.peek() <= minArr[i]) { stack.pop(); } if (!stack.isEmpty() && stack.peek() < nums[i]) { ans = true; return ans; } stack.push(nums[i]); } } return ans; }}
复制代码


总结

  • 这个题目初看有点懵,再看就明白了题目含义,是一种模式匹配问题。

  • 代码解题使用了单调栈数据结构。为了维护栈的单调性,插入新元素时,需要保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。

  • 坚持每日一题,加油!


发布于: 2021 年 03 月 24 日阅读数: 8
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】132模式Java题解