给定一个整数序列：a1, a2, …, an，一个132模式的子序列 ai, aj, ak 被定义为：当 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/132-pattern 36 ms 17.5 MB
1. 题目
i < j < k 时，ai < ak < aj。
设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。注意：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].
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。2. 解题
当5要入栈时，不满足递减了
更新第二大数Ak为栈顶，弹栈，继续检查，最后栈内空，Ak=4，push 5
下一个数 3 < Ak(第二大)，存在class Solution { public: bool find132pattern(vector<int>& nums) { if(nums.size() < 3) return false; stack<int> 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; } };
本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。
ImovieBox网页视频下载器 下载地址: ImovieBox网页视频下载器-最新版本下载
本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.
阅读和此文章类似的: 全球云计算
官方软件产品操作指南 (170)
