132 模式

描述:给你一个 n 个整数的序列 a1,a2,...,an,一个 132 模式是对于一个子串 ai,aj,ak,满足 i < j < k 和 ai < ak < aj。设计一个算法来检查输入的这 n 个整数的序列中是否存在132模式。
n 会小于 20,000。
思路:维护一个栈和一个变量third,其中third就是第三个数字,也是pattern132中的2,栈里面按顺序放所有大于third的数字,也是pattern132中的3,那么我们在遍历的时候,如果当前数字小于third,即pattern 132中的1找到了,我们直接返回true即可,倒序遍历依次更新st,thrid值
注意事项:i,j,k可以是不连续的

class Solution {
public:
    /**
     * @param nums: a list of n integers
     * @return: true if there is a 132 pattern or false
     */
    bool find132pattern(vector<int> &nums) {
        // write your code here
        int len = nums.size();
        if( len < 2 )
        {
            return false;
        }
         std::stack<int> st;
         int thrid = INT_MIN;
         for( int i = len - 1; i >= 0; --i)
         {
             if( nums[i] < thrid )
             {
                 return true;
             }
             while( !st.empty() && nums[i] > st.top() )
             {
                 thrid = st.top();
                 st.pop();
             }
             st.push(nums[i]);
        }
        return false;
    }
};
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 题目 概述:给定一个整数数组,判断该数组里是否有满足132模式的序列(132模式:序列中的第一个数 < 序列中的第...
    三次元蚂蚁阅读 351评论 0 1
  • 1)这本书为什么值得看: Python语言描述,如果学的Python用这本书学数据结构更合适 2016年出版,内容...
    孙怀阔阅读 12,625评论 0 15
  • 在C语言中,五种基本数据类型存储空间长度的排列顺序是: A)char B)char=int<=float C)ch...
    夏天再来阅读 3,421评论 0 2
  • 每天晚上是属于我的快乐时光。因为每天的这个时间我总能看到快乐的模样。 年近六十的老妈已忙碌一天,直...
    红薇儿阅读 485评论 1 6
  • 任务: 1、早睡早起:23点前休息,6:20-6:40。 2、专业课学习,包括:课件、练习、复习,完成任意一项。 ...
    大眼妹宝贝阅读 134评论 0 1