LeetCode456-132模式

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/132-pattern/

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

题目详述

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

注意：n 的值小于15000。

示例1:

1
2
3
4
5
输入: [1, 2, 3, 4]

输出: False

解释: 序列中不存在132模式的子序列。

示例 2:

1
2
3
4
5
输入: [3, 1, 4, 2]

输出: True

解释: 序列中有 1 个132模式的子序列： [1, 4, 2].

示例 3:

1
2
3
4
5
输入: [-1, 3, 2, 0]

输出: True

解释: 序列中有 3 个132模式的的子序列: [-1, 3, 2], [-1, 3, 0] 和 [-1, 2, 0].

题目详解

  • 从后向前遍历数组，保持 aj 和 ak 尽可能的大，这样才可能给 ai 更大的可能性满足 132 模式。
  • 这就需要用到单调栈，当当前元素大于栈顶元素时，弹出栈顶元素赋给 ak 直至当前元素不大于栈顶元素，最后 push 当前元素入栈。
  • 遍历过程中，每次检查当前元素（即 ai）是否小于 ak，若满足则达成了 132 模式。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class LeetCode_00456 {

    public boolean find132pattern(int[] nums) {
        int ak = Integer.MIN_VALUE;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = nums.length - 1; i >= 0; --i) {
            if (nums[i] < ak) {
                return true;
            }
            while (!stack.isEmpty() && nums[i] > stack.peek()) {
                ak = stack.pop();
            }
            stack.push(nums[i]);
        }
        return false;
    }
}