132模式

@author: sdubrz
@date: 2020.0412
题目难度： 中等
考察内容： 栈
原题链接 https://leetcode-cn.com/problems/132-pattern/
题目的著作权归领扣网络所有，商业转载请联系官方授权，非商业转载请注明出处。
解题代码转载请联系 lwyz521604#163.com
           

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

**注意：**n 的值小于15000。

示例1:

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

输出: False

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

示例 2:

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

输出: True

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

示例 3:

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

输出: True

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

通过次数

7431

提交次数

28142

常规方法

这道题官方给的标签是栈，但是我没有想出用栈的实现方式。最后写了一个用 ArrayList 实现的版本，提交之后通过了，但是排名比较低。主要的思路就是对于一个数对(a, b)，其中 a<b ，判断它们后面的数 c 是否满足 a<c<b 。从左到右扫描一遍数组，用两个 ArrayList 分别存储 a 和 b。时间复杂度应该是 O ( n 2 ) O(n^2) O(n2)的吧。

Java实现如下：

class Solution {
   public boolean find132pattern(int[] nums) {
		if(nums.length<3) {
			return false;
		}
		
		ArrayList<Integer> maxs = new ArrayList<>();
		ArrayList<Integer> mins = new ArrayList<>();
		
		int minIndex0 = 0;
		int maxIndex0 = 0;
		
		int itex = 1;
		while(itex<nums.length && minIndex0>=maxIndex0) {
			if(nums[itex]<nums[minIndex0]) {
				minIndex0 = itex;
				maxIndex0 = itex;
			}else if(nums[itex]>nums[maxIndex0]) {
				maxIndex0 = itex;
			}
			
			itex++;
		}
		
		if(minIndex0>=maxIndex0) {
			return false;
		}
		
		maxs.add(nums[maxIndex0]);
		mins.add(nums[minIndex0]);
		
		while(itex<nums.length) {
			// System.out.println("current number: "+nums[itex]);
			int n = maxs.size();
			for(int i=n-1; i>=0; i--) {
				if(nums[itex]>mins.get(i) && nums[itex]<maxs.get(i)) {
					return true;
				}
			}
			
			if(maxs.size()==mins.size()) { // 一样长
				if(nums[itex]>maxs.get(n-1)) {
					maxs.set(n-1, nums[itex]);
				}else if(nums[itex]<mins.get(n-1)){
					mins.add(nums[itex]);
				}
			}else{  // 最大链表不可能比小链表长
				if(nums[itex]>mins.get(mins.size()-1)) {
					maxs.add(nums[itex]);
				}
			}
			
			itex++;
		}
		
		
		return false;
	}
}
           

在 LeetCode 系统中提交的结果如下

执行结果： 通过 显示详情
执行用时 : 266 ms, 在所有 Java 提交中击败了 22.65% 的用户
内存消耗 : 40.4 MB, 在所有 Java 提交中击败了 35.29% 的用户
           

栈方法

下面是官方给出的栈的实现方法

这个方法的时间复杂度降到了 O ( n ) O(n) O(n)。官方代码如下

public class Solution {
    public boolean find132pattern(int[] nums) {
        if (nums.length < 3)
            return false;
        Stack < Integer > stack = new Stack < > ();
        int[] min = new int[nums.length];
        min[0] = nums[0];
        for (int i = 1; i < nums.length; i++)
            min[i] = Math.min(min[i - 1], nums[i]);
        for (int j = nums.length - 1; j >= 0; j--) {
            if (nums[j] > min[j]) {
                while (!stack.isEmpty() && stack.peek() <= min[j])
                    stack.pop();
                if (!stack.isEmpty() && stack.peek() < nums[j])
                    return true;
                stack.push(nums[j]);
            }
        }
        return false;
    }
}