本文共 969 字，大约阅读时间需要 3 分钟。

1. 题目

给定一个整数序列：a1, a2, …, an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak < aj。

注意：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].

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/132-pattern

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

class Solution {
   public:    bool find132pattern(vector
   
    & nums) {
       	if(nums.size() < 3)    		return false;    	stack
    
      s;//单调递减栈    	int Ak = INT_MIN;//第二大的数    	for(int i = nums.size()-1; i >= 0; --i)    	{
       		if(Ak > nums[i])    			return true;    		while(!s.empty() && nums[i] > s.top())    		{
       			Ak = s.top();    			s.pop();    		}    		s.push(nums[i]);    	}    	return false;    }};
    
   

36 ms 17.5 MB

转载地址：https://michael.blog.csdn.net/article/details/105688840 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！