456. 132 Pattern | 456. 132 模式（单调栈）

痛定思痛。 2022-09-06 10:22 129阅读 0赞

## 题目 ##

[https://leetcode.com/problems/132-pattern/][https_leetcode.com_problems_132-pattern]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

参考：[【负雪明烛】从「暴力求解」到「单调栈」][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

class Solution { 
        public boolean find132pattern(int[] nums) { 
            int L = nums.length;
    
            int[] leftMin = new int[L];
            leftMin[0] = nums[0];
            for (int i = 1; i < L; i++) { 
                leftMin[i] = Math.min(nums[i], leftMin[i - 1]);
            }
    
            Stack<Integer> stack = new Stack<>(); // 单调不增栈
            for (int i = L - 1; i > 0; i--) { 
                while (!stack.isEmpty() && stack.peek() < nums[i]) { 
                    if (stack.pop() > leftMin[i - 1]) return true;
                }
                stack.push(nums[i]);
            }
    
            return false;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

[https_leetcode.com_problems_132-pattern]: https://leetcode.com/problems/132-pattern/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/10b7b8c3bcc2487b8e5064556a204652.png
[Link 1]: https://leetcode-cn.com/problems/132-pattern/solution/fu-xue-ming-zhu-cong-bao-li-qiu-jie-dao-eg78f/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/0ba091cda505466a850738c5009c79a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/f6b0ce5f82b24d7facd9077a87d5e618.png