LeetCode 456. 132 模式

题目描述
- 法一：暴力穷举
- 法二：单调栈 + 维护3

题目描述

给你一个整数数组 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) 的解决方案吗？

地址：https://leetcode-cn.com/problems/132-pattern/
2021/03/24

法一：暴力穷举
子序列，满足 132 模式（暴力枚举 3）
- 暴力枚举两个位置，i 和 j 相当于 132 中的 1 和 3，然后在 j 的右边寻找比 numsi 大且比numsk 小的数，若存在则返回true，否则返回false
- 而且在枚举移动过程中要保证numsi的值小于numsj
时间复杂度 O(n²)

空间复杂度 O(1)

# i, j, k
# numsi < numsk < numsj
class Solution(object):
  def find132pattern(self, nums):
      size = len(nums)
      numsi = nums[0]
      for j in range(1, size):# 枚举 j
          for k in range(size - 1, j, -1): # 在 j 的右边寻找 k
              if (numsi < nums[k] and nums[k] < nums[j]): # 为什么and 能过，但是 & 不能过？
                  return True
          # 确保numsi < numsj
          numsi = min(numsi, nums[j])
      return False

class Solution {
public:
  bool find132pattern(vector<int>& nums) {
      int len = nums.size();
      int numsi = nums[0];
      for (int j=1; j < len; j++) { // 因为需要 numsi < numsj,所以可以提前判断一下 
          if (numsi > nums[j]) {
              numsi = nums[j];
              continue;
          }
          for (int k=len-1; k>j; k--) {
              if ((numsi < nums[k]) && (nums[k] < nums[j])) {
                  return true;
              }
          }
      }
      return false;
  }
};

法二：单调栈 + 维护3

为了得到 132 模式中的 2，并且使 2 尽可能的大（学的太少，想不到，脑瓜子嗡嗡的）
- 在 j 之前找比numsk小的数numsi，在 j 之后找比numsj 小的数，以 j 为中心
- 从右往前遍历维护一个单调（增）栈
- 遍历所有的 i ，寻找符合条件的（numsj, numsk），只要numsk > numsi 就可以了
- 只要判断（numsj, numsk）最大的组合就行，numsj 只和numsk 有关系与numsi无关
栈里里面的是 3 ，出栈的是 2，要寻找的是 1，所以只要能找到 1 则表明存在该模式
单调栈就是从数组中找到左右两边比你大的数或者比你小的数而且时间复杂度为O(N)
时间复杂度：O(n)
空间复杂度：O(n)

巨人的肩膀：https://www.cnblogs.com/grandyang/p/6081984.html

class Solution(object):
  def find132pattern(self, nums):
      stack = []
      right = float("-inf")
      for i in range(len(nums)-1, -1, -1):
          if nums[i] < right: 
              return True
          while stack and stack[-1] < nums[i]:
              right = stack.pop()
          stack.append(nums[i])
      return False

```cpp /*

// 逆序入栈，出栈则表明右边已经存在比 3 小的数 2 了，只要继续在左边能找到一个比 2 小的数就可以 [1 3 7 6 8]

8 two = INT_MIN 6 8 two = INT_MIN 7 8 two = 6 3 < two 直接返回 true 即存在 3 7 6

*/ class Solution { public: bool find132pattern(vector& nums) { stack st; int two = INT_MIN; for (int i = nums.size() - 1; i >= 0; i—) { // 遍历每一个 i if (nums[i] < two) return true; while (!st.empty() && nums[i] > st.top()) { two = st.top(); // 或者你实时维护一个次大的数也可以 st.pop(); } st.push(nums[i]); } return false; } }; ```

题目描述

法一：暴力穷举

法二：单调栈 + 维护3