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