# 456 题 132 模式

# 题目链接

# 难度:中等

# 思路分析:

#

#

#

#

#

#

#

#

#

#

#

#

#

#

# 代码:

贪心:

var find132pattern = function(nums) {
  if (nums.length <= 2) return false;
  let min = nums[0];
  for (let i = 1; i < nums.length - 1; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      // 比主循环大一个索引 当前循环值 比最小值大, 又比主循环值小 即满足
      if (nums[j] > min && nums[j] < nums[i]) return true;
    }
    min = Math.min(min, nums[i]); // 遍历过的值的最小值
  }
  return false;
};
1
2
3
4
5
6
7
8
9
10
11
12

var find132pattern = function(nums) {
  if (nums.length <= 2) return false;
  const min = [nums[0]];
  const stack = [];
  // 数组前i项最小的数字存在一个数组min内
  for (let i = 1; i < nums.length; i++) {
    min[i] = Math.min(min[i - 1], nums[i]);
  }
  // 倒序
  for (let i = nums.length - 1; i > 0; i--) {
    // 当前项不是最小值
    if (nums[i] > min[i]) {
      // 栈内数据小于当前值的最小值 从min的大值开始
      while (stack.length !== 0 && stack[stack.length - 1] <= min[i]) {
        stack.pop();
      }
      // 栈内(之前遍历的)数据比当前值小 即满足 l1<l3<l2的需求
      if (stack.length !== 0 && stack[stack.length - 1] < nums[i]) {
        return true;
      }
      stack.push(nums[i]); // 比最小值大
    }
  }
  return false;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 鼓励我一下:

觉得还不错的话,给我的项目点个star

# 点个Star支持我一下~

最后更新时间: 7/2/2020, 4:27:35 PM