132序列

# -*- 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