132序列

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return bool布尔型
     */
    bool find132Subseq(vector<int>& nums) {
        // write code here
        stack<int> st;
        st.push(nums[0]);
        for(int i=1;i<nums.size();i++)
        {
            int ctl=-1;
            while(!st.empty()&&(st.top()>nums[i]))
            {
                if(st.size()>=2)
                {
                    ctl=0;
                }
                st.pop();
            }
            if(!st.empty())
            {
                ctl++;
            }
            if(ctl==1)
            {
                return true;
            }
            st.push(nums[i]);
        }
        return false;
    }
};

public boolean find132Subseq (ArrayList<Integer> arr) {
        // write code here
        Integer[] nums = arr.toArray(new Integer[0]);
        int min = nums[0];
        int max = nums[1]>nums[0]?nums[1]:nums[0];
        for(int i=2;i<nums.length;i++){
            if(nums[i]>min&&nums[i]<max){
                return true;
            } else if(nums[i]>min){
                max=Math.max(max,nums[i]);
            } else if(nums[i]<min){
                min=Math.min(min,nums[i]);
                max=min;
            }
            
        }
        return false;
        
    }

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @return bool布尔型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/eae8142169a74ad7884bb5dca3264128?tpId=196&tqId=40515&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    算法：
        132序列：i < j < k 且 nums[i] < nums[k] < nums[j]，这里我们借助单调不减栈stack，存储元素的下标，使用flag表示是否存在逆序对
        遍历nums：
            若栈不空 且 存在逆序对：
                flag置为True，弹出栈顶
            若找到逆序对：
                将stack中对应元素与nums[i]相等的下标，全部弹出
                若此时stack仍存在元素，说明满足132序列；否则重置flag=False
        遍历结束，返回False
    复杂度：
        时间复杂度：O(n)
        空间复杂度：O(n)
    """

    def find132Subseq(self, nums):
        # write code here
        n = len(nums)
        stack, flag = [], False

        for i in range(n):
            while stack and nums[stack[-1]] > nums[i]: # 找到逆序对nums[k] < nums[j]，需要再判断是否满足nums[i] < nums[k]
                flag = True # flag表示是否找到逆序对
                stack.pop()
            if flag:
                while stack and nums[stack[-1]] == nums[i]: # 比如[1, 2, 1]不合符条件
                    stack.pop()
                if stack: # [2, 3, 1]
                    return True
                else: # 比如[3, 2, 1]，属于无效逆序对，重置flag = False
                    flag = False
            stack.append(i)

        return False


if __name__ == "__main__":
    sol = Solution()

    # nums = [1, 2, 3, 2, 1]

    # nums = [82, 78, 12, 42, 65]

    # nums = [2, 2, 2, 2]

    nums = [1, 2, 1]

    res = sol.find132Subseq(nums)

    print res