LeetCode456. 132模式

电玩女神 2022-11-12 13:59 141阅读 0赞

难度：`中等`  
题目描述：

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

示例 1：

> 输入：nums = \[1,2,3,4\]  
> 输出：false  
> 解释：序列中不存在 132 模式的子序列。

示例 2：

> 输入：nums = \[3,1,4,2\]  
> 输出：true  
> 解释：序列中有 1 个 132 模式的子序列： \[1, 4, 2\] 。

示例 3：

> 输入：nums = \[-1,3,2,0\]  
> 输出：true  
> 解释：序列中有 3 个 132 模式的的子序列：\[-1, 3, 2\]、\[-1,3, 0\] 和 \[-1, 2, 0\] 。

提示：

>     n == nums.length
>     1 <= n <= 104
>     -109 <= nums[i] <= 109

class Solution { 
    public:
        bool find132pattern(vector<int>& nums) { 
            int n=nums.size();
            if(n<3){ 
                return false;
            }
            for(int min_n=0;min_n<n-2;min_n++){ 
                int min=nums[min_n];
                int mid,max=nums[min_n];
                int tmp=n;
                for(int i=min_n+1;i<n;i++){ 
                    if(nums[i]>min){ 
                        if(nums[i]>max){ 
                            max=nums[i];
                            tmp=i;
                        }else if(nums[i]<max&&i>tmp){ 
                            return true;
                        }
                    }
                }
            }
            return false;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，141人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode_单调栈_中等_456.132 模式

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列由三个整

清疚/ 2023年10月06日 23:36/ 0 赞/ 23 阅读

相关 leetcode 456 132模式

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

野性酷女/ 2023年07月01日 15:57/ 0 赞/ 5 阅读

相关【算法积累】132模式

LeetCode 456. 132模式难度中等给定一个整数序列：a1, a2, …, an，一个132模式的子序列ai, aj, ak被定义为：当i < j <

川长思鸟来/ 2022年12月23日 11:16/ 0 赞/ 178 阅读

相关 leetcode#456. 132 模式（图解）

题目给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列由三个整数 nums\[i\]、nums\[j\] 和 nums\[k\] 组成，并同时

悠悠/ 2022年11月13日 04:11/ 0 赞/ 132 阅读

相关 456. 132模式

456. 132模式给你一个整数数组 `nums` ，数组中共有 `n` 个整数。132 模式的子序列由三个整数 `nums[i]`、`nums[j]` 和 `num

我就是我/ 2022年11月13日 00:48/ 0 赞/ 156 阅读

相关 LeetCode456. 132模式

难度：`中等` 题目描述： > 给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列由三个整数 nums\[i\]、nums\[j\] 和 num

电玩女神/ 2022年11月12日 13:59/ 0 赞/ 142 阅读

相关 456. 132 模式

> 给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列由三个整数 nums\[i\]、nums\[j\] 和 nums\[k\] 组成，并同时满足：i

超、凢脫俗/ 2022年10月07日 00:53/ 0 赞/ 149 阅读

相关 Leetcode 456. 132 模式（DAY 188）---- 二分查找学习期

文章目录原题题目代码实现（首刷绝大部分看解单调栈- - 反着来） -------------------- 原题题目 -----

旧城等待，/ 2022年09月15日 12:43/ 0 赞/ 191 阅读

相关 456. 132 Pattern | 456. 132 模式（单调栈）

题目 [https://leetcode.com/problems/132-pattern/][https_leetcode.com_problems_132-patte

痛定思痛。/ 2022年09月06日 10:22/ 0 赞/ 149 阅读

相关 leetcode 456. 132 Pattern 132模式元素寻找 + 一个很棒的利用stack的做法

Given a sequence of n integers a1, a2, …, an, a 132 pattern is a subsequence ai, aj, ak

分手后的思念是犯贱/ 2022年06月04日 09:08/ 0 赞/ 155 阅读