2021/3/24 132模式

题目描述

描述转载自力扣《456. 132模式》
给你一个整数数组 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(n logn) 或 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] 。

解题思路

1. 的情况很容易想出来，我们使用暴力算法，维护 132 中的 3，也就是说我们遍历的数就是 3 对应的数，每次遍历结束之前都记录一下这个 3 和前面的 1 哪个更小，记下这个最小值，赋值给 1。在遍历 3 的过程中，嵌套遍历 3 右边的所有元素，这样我们就得到了三个值，然后比较 1 2 3 之间的关系，如果符合 132 排列，那么就返回 true；
   

2. 接下来我们使用 的方法。我们先维护一个数组 leftMin，存储原数组 nums 对应位置上的左边的最小值；
   
   然后我们维护一个栈，从 nums 数组的末尾向前遍历，若遇到比栈顶小的元素则放入栈中，若比栈顶大则将元素取出直到比栈顶元素小为止。这样我们就可以获得三个数字，一个是当前遍历 nums 的索引 j 对饮的 leftMin[j]，一个是 nums[j]，一个是取出的栈顶元素 k，我们比较 i j k，如果 j > k > i，则返回 true。

Java代码实现

1. 暴力解法

class Solution {
    public boolean find132pattern(int[] nums) {
        int i = nums[0];
        for (int j = 1; j < nums.length - 1; ++j) {
            for (int k = j + 1; k < nums.length; ++k) {
                if (nums[j] > nums[k] && nums[k] > i) return true;
            }
            i = nums[j] < i ? nums[j] : i;
        }
        return false;
    }
}

2. 使用单调栈

class Solution {
    public boolean find132pattern(int[] nums) {
        // 计算左边最小值映射表
        int[] leftMin = new int[nums.length];
        leftMin[0] = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length - 1; ++i) {
            leftMin[i + 1] = Math.min(nums[i], leftMin[i]);
        }
        // 从后往前遍历，维护3
        Stack<Integer> stack = new Stack<>();
        int k = Integer.MIN_VALUE;
        for (int i = nums.length - 1; i > 0; --i) {
            while (!stack.empty() && stack.peek() < nums[i]) {
                k = Math.max(k, stack.pop());
            }
            if (nums[i] > k && k > leftMin[i]) return true;
            stack.push(nums[i]);
        }
        return false;
    }
}