【LeetCode】132 模式 Java 题解

关注

发布于: 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

原文链接:【http://xie.infoq.cn/article/5085f6e9bf523de5e079af6ee】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】132 模式 Java 题解

题目

代码

总结

HQ数字卡

评论