leetcode#456. 132 模式（图解）

悠悠 2022-11-13 04:11 122阅读 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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/132-pattern  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 代码 ##

class Solution {
        
    public:
        bool find132pattern(vector<int>& nums) {
        
            stack<int> st;
            int k=INT_MIN;
            for(int i=nums.size()-1;i>=0;i--){
        
                if (nums[i]<k) return true;
                while(!st.empty()&&nums[i]>st.top()){
        
                    k=st.top();
                    st.pop();
                }
                if(nums[i]>k){
        
                    st.push(nums[i]);
                }
            }
            return false;
        }
    };

## 图解 ##

感觉单调栈的做法比较难理解，所以按步骤画了图有助于理解  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 7]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]: /images/20221022/71dfb7011d444a6d9ddd12ca2f92eb72.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 1]: /images/20221022/3bdd89319d5740038d128ebe2ea578db.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 2]: /images/20221022/04c0d85d125240d4b73afa2c4bc276aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 3]: /images/20221022/1c3c78be121844908a675c272f7c84ed.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 4]: /images/20221022/96c76652e415408dbf740c79e2d5a374.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 5]: /images/20221022/458d59499fb14de1a050d968951e550f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 6]: /images/20221022/c4ccc8249be64476ae4bf9c08c00f808.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 7]: /images/20221022/b516bb55d19c45e88da9a1aea6a2bd5c.png