2021.3.24

456. 132模式

https://leetcode-cn.com/problems/132-pattern/

给你一个整数数组 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] 。

学到的知识点：单调栈
&emsp;今天这一题我看到题的第一反应是使用一个单调递增栈从前往后地记录数字，这样必定可以记录到能够作为1的数和能够作为3的数，结果在[3,5,0,1,4]这个数列面前倒下了。（然后看了一眼评论区）
&emsp;重新思考：作为1的数要是一个相当小的数，作为3的数要是一个尽量大的数，作为2的数要是一个比3小，但是尽量大的数。
&emsp;由于本题2在3的右边，所以要找到一个尽量大的2，就需要从右往左进行查找，每当找到3时就更新2的值（使其尽量的大），这个过程可以使用一个单调递减栈完成（对每个2，要找到第一个比他大的数作为3）。如果有过出栈行为，则说明有一组2和3，那么这时只要找到一个比2小的1就可以了。
&emsp;所以，在每次找到一个新的3时，将最后一个出栈（尽量大）的数设置为2，往前读到新的数时，如果他比这个2小，那么他就是1。即：单调栈维护的是3，int two维护的是2，枚举的是1。

最终代码如下：

public class Solution {
    public bool Find132pattern(int[] nums) {
        Stack<int> sta = new Stack<int>();
        int two = int.MinValue;
        for(int i=nums.Length-1;i>=0;i--){
            if(nums[i]<two){
                return true;
            }
            if(sta.Count()==0||nums[i]<sta.Peek()){
                sta.Push(nums[i]);
            }
            else{
                while(sta.Count()>0&&sta.Peek()<nums[i]){
                    two=sta.Pop();
                }
                sta.Push(nums[i]);
            }
        }
        return false;
    }
}