LeetCode_单调栈_中等_456.132 模式

清疚 2023-10-06 23:36 92阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列由三个整数 nums\[i\]、nums\[j\] 和 nums\[k\] 组成，并同时满足：i < j < k 和 nums\[i\] < nums\[k\] < nums\[j\] 。

如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。

**示例 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\] 。

**提示：**  
n == nums.length  
1 <= n <= 2 \* 105  
\-109 <= nums\[i\] <= 109

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/132-pattern  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 2.思路 ##

（1）暴力穷举法  
该方法比较容易想到，即穷举所有的子序列 \[nums\[i\], nums\[j\], nums\[k\]\] (i < j < k)，如果存在满足 nums\[i\] < nums\[k\] < nums\[j\] 的子序列，则直接返回 true。如果穷举结束之后仍未找到，则说明数组 nums 中不存在 132 模式的子序列，返回 false 即可。需要注意的是，该方法的时间复杂度较高，为 O(n3)，在 LeetCode 上提交会出现“超出时间限制”的提示！

（2）单调栈  
思路参考[该 LeetCode 用户题解][LeetCode]。

## 3.代码实现（Java） ##

//思路1————暴力穷举法
    class Solution {
        
        public boolean find132pattern(int[] nums) {
        
            for (int i = 0; i < nums.length - 2; i++) {
        
                for (int j = i + 1; j < nums.length - 1; j++) {
        
                    if (nums[i] >= nums[j]) {
        
                        continue;
                    }
                    for (int k = j + 1; k < nums.length; k++) {
        
                        if (nums[i] < nums[k] && nums[k] < nums[j]) {
        
                            return true;
                        }
                    }
                }
            }
            return false;
        }
    }

//思路2————单调栈
    class Solution {
        
        public boolean find132pattern(int[] nums) {
        
            Stack<Integer> stack = new Stack<>();
            int nums_k = Integer.MIN_VALUE;
            //从后往前遍历
            for (int i = nums.length - 1; i >= 0; i--) {
        
            	//由于 nums_k
                if (nums[i] < nums_k) {
        
                    return true;
                }
                //维护单调递减栈（栈顶元素最小，栈底元素最大）
                while (!stack.isEmpty() && stack.peek() < nums[i]) {
        
                    nums_k = Math.max(nums_k, stack.pop());
                }
                stack.push(nums[i]);
            }
            return false;
        }
    }

[LeetCode]: https://leetcode.cn/problems/132-pattern/solution/xiang-xin-ke-xue-xi-lie-xiang-jie-wei-he-95gt/