456. 132 Pattern

Leetcode link

背景知识

本题要求我们找出一个数组中是否有 “132” 组合，注意是允许不连续的

考虑到时间复杂度，我们把三个数字全部遍历一次肯定会 OT

那么我们可以想一下有没有可能遍历其中一个就可以找到结果呢？答案是可以的，而且有三种方法：

1. 遍历其中的 1，也就是最小的那个数，这样一来我们只要在它的右边找出一对 (j,k)，使得 j>k 就好
2. 遍历其中的 3，也就是最大的数，这样一来，我们得在它的左边找到 “小于它的最小的数“，在它右边找到 ”小于它的最大的数“
3. 遍历其中的 2，也就是中间的数，思路与方法一差不多，只是变成要在它的左边找一对 (i,j)，使得 i<j。

解题思路——方法一

我们来讲一下方法一，因为方法一只要在保证 j>k 的条件下，记录最大的 k 拿来跟遍历的数比较就好。

举个例子，现在有一组数组 [3, 4, 6, 4, 3, -1, 6]，我们维护一个单调递减栈，其中存放着比 j 小的同时下标比 j 大的数。

我们从后往前遍历：

• 数字 6：此时栈为空，我们把它入栈；栈顶为 6
• 数字 -1：-1 < 6 入栈；栈顶为 -1
• 数字 3：3 > -1，表示它有可能是 j，这个时候我们可以把 k 设置成 “比 j 小的最大值”；在这里，k = -1；把 3 入栈
• 数字 4：4 > k，表示 4 不符合被当成 "1" 的条件；4 > 3，表示它有可能是 j；更新 k 为 3；把 4 入栈
• 数字 6：6 > 3，不能为 "1"；6 > 4，更新 k 为 4；把 6 入栈
• 数字 4：4 == 4，不能为 "1"；4 < 6，不更新 k；把 4 入栈
• 数字 3：3 < 4，可以当成 "1"，这下子三个数都找到了，返回 true

注：在找比 j 小的最大值的时候顺便会把栈里面比 j 小的数全部丢掉，因为没用了

下面的表展示了在遍历过程栈与 k 的变化：

C++

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
    // 遍历 "132" 中最小的 "1"
    // 单调递减的栈
    stack<int> st;
    // k: "132" 中的 "2"
    int k = INT_MIN;

    for (int i = nums.size() - 1; i >= 0; i--) {
      // 只有当 k 有被更新过，当前元素才可能小于它（才有可能是 "1"），而后面的循环表示 k 要被更新过必须有比 k 大的数在栈中
      if (nums[i] < k) {
        return true;
      }
      // 如果找到了一个比 "2" 大的数，表示它有可能成为
      // "3"，这个时候只要保留它右边比它小的 “最大值” 就好
      while (!st.empty() && (nums[i] > st.top())) {
        k = max(k, st.top());
        st.pop();
      }
      // 只要 k 有被更新过，说明这个栈里面必有比 k 大的数
      st.push(nums[i]);
    }
    return false;
  }
};

Javascript

var find132pattern = function(nums) {
    let stack = [];
    let k = Number.MIN_SAFE_INTEGER;
    for(let i=nums.length-1;i>=0;i--) {
        if(nums[i]< k) {
            return true;
        }

        while(stack.length!==0 && nums[i] > stack[stack.length-1]) {
            k = Math.max(k, stack.pop());
        }
        stack.push(nums[i]);
    }
    return false;
};

解题思路——方法三

思路来源：https://leetcode-cn.com/problems/132-pattern/solution/132mo-shi-by-leetcode-solution-ye89/850676

因为觉得思路太好了所以搬运记录一下

这个方法是用了遍历 "132" 中的 "2"，它可以让我们从前往后遍历，如果今天的数据是流的话就只能用这个方法了

这个方法我们需要维护一个栈，还有一个数组，其中数组 leftMin 保存的是当前元素左边最小的数

我们的目标是找到一个数小于栈顶元素的同时，栈顶元素左边的最小值也小于它就返回 true

一样用 [3, 4, 6, 4, 3, -1, 6] 来做例子吧：

• 数字 3：目前栈为空，直接把 3 入栈；leftMin[0] = 3

• 数字 4：4 > 3，表示它不能被当成 j，将 3 出栈，4入栈；leftMin[1] = 3

• 数字 6：6 > 4，一样将 4 出栈，6入栈；leftMin[2] = 3

• 数字 4：4 < 6，表示它有可能是 j，然后我们看一下栈顶元素左边元素最小值是 3，3 < 4，bingo～

注：在代码中为了访问方便栈中存放的其实是下标，这里写元素是为了理解方便

下面的表展示了在遍历过程栈与数组的变化：

C++

class Solution {
 public:
  bool find132pattern(vector<int>& nums) {
    stack<int> st;
    // 存放当前元素左边最小的数
    vector<int> leftMin{INT_MAX};
    for (int i = 0; i < nums.size(); i++) {
      // 把比 nums[i] 小或者等于的数全部出栈
      while (!st.empty() && (nums[st.top()] <= nums[i])) {
        st.pop();
      }
      // 如果比当前大的数左边有比当前数小的数的时候，表示存在
      if (!st.empty() && (leftMin[st.top()] < nums[i])) {
        return true;
      }
      st.push(i);
      leftMin.push_back(min(leftMin.back(), nums[i]));
    }
    return false;
  }
};

Javascript

var find132pattern = function(nums) {
    let stack = [];
  // 存放当前元素左边最小的数
    let leftMin = [Number.MAX_SAFE_INTEGER];
    for(let i=0;i<nums.length;i++) {
      // 把比 nums[i] 小或者等于的数全部出栈
        while((stack.length > 0) && (nums[stack[stack.length-1]] <= nums[i])) {
            stack.pop();
        }
      // 如果比当前大的数左边有比当前数小的数的时候，表示存在
        if((stack.length > 0) && leftMin[stack[stack.length-1]] < nums[i]) {
            return true;
        }
        stack.push(i);
        leftMin.push(Math.min(leftMin[i], nums[i]));
    }
    return false;
};