一、题目

给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。

如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。

点击查看原题
难度级别： 中等

二、思路

1）TreeMap

使用暴力法，将会先确定j位置，找到j位置元素之前的最小值nums[i]，然后在j位置后面找到位置k，让nums[i] < nums[k] < nums[j]，如果能够找到k，则返回true，没有找到k就将j后移一位
这里将暴力法中查找k的方式，使用TreeMap加速查找

2）单调栈

题目要求找到132模式，让i<j<k，且nums[i] < nums[k] < nums[j]，先找到k和j，使用递减栈从后面开始遍历，将递减栈出栈的最大元素为nums[k]，如果遍历到元素小于nums[k]，那么就找到了132模式的序列，下面解释一下为什么这么做：
1、递减栈能够确保栈中元素是递减排列，当新遍历的元素大于栈顶元素，则出栈
2、k指向的元素为出栈的最大元素，则可以确定，nums[k]一定是一个尽可能接近nums[j]的数
3、由于nums[k]和nums[j]形成了nums[k]<nums[j]，接下来只需要遍历到元素小于nums[k]的情况，就找到了序列

三、代码

1）TreeMap

  1. class Solution {
  2.     public boolean find132pattern(int[] nums) {
  3.         TreeMap<Integer, Integer> tm = new TreeMap();
  4.         int leftMin = nums[0];
  5.         for (int i = 1; i < nums.length; i++) {
  6.             tm.put(nums[i], tm.getOrDefault(nums[i], 0) + 1);
  7.         }
  8.         for (int i = 1; i < nums.length - 1; i++) {
  9.             if (tm.get(nums[i]) == 1) {
  10.                 tm.remove(nums[i]);
  11.             } else {
  12.                 tm.put(nums[i], tm.get(nums[i]) - 1);
  13.             }
  14.             if (leftMin > nums[i]) {
  15.                 leftMin = nums[i];
  16.                 continue;
  17.             }
  18.             Integer t = tm.lowerKey(nums[i]);
  19.             if (t != null && t > leftMin) {
  20.                 return true;
  21.             }
  22.         }
  23.         return false;
  24.     }
  25. }

时间复杂度为O(nlogn)，空间复杂度为O(n)

2）单调栈

  1. class Solution {
  2.     public boolean find132pattern(int[] nums) {
  3.         List<Integer> desc = new ArrayList();
  4.         int k = Integer.MIN_VALUE;
  5.         for (int j = nums.length - 1; j >= 0; j--) {
  6.             if (k > nums[j]) {
  7.                 return true;
  8.             }
  9.             while (desc.size() != 0 && desc.get(desc.size() - 1) < nums[j]) {
  10.                 k = Math.max(k, desc.get(desc.size() - 1));
  11.                 desc.remove(desc.size() - 1);
  12.             }
  13.             desc.add(nums[j]);
  14.         }
  15.         return false;
  16.     }
  17. }

时间复杂度为O(n)，空间复杂度为O(n)