【算法积累】132模式

川长思鸟来 2022-12-23 11:16 153阅读 0赞

## LeetCode 456. 132模式 ##

**难度** 中等

给定一个整数序列：a1, a2, …, an，一个132模式的子序列ai, aj, ak被定义为：当i < j < k时，ai < ak < aj。设计一个算法，当给定有n个数字的序列时，验证这个序列中是否含有132模式的子序列。  
注意：n的值小于15000。

**示例1**

输入: [1, 2, 3, 4]
    输出: False
    解释: 序列中不存在132模式的子序列。

**示例2**

输入: [3, 1, 4, 2]
    输出: True
    解释: 序列中有1个132模式的子序列： [1, 4, 2].

**示例3**

输入: [-1, 3, 2, 0]
    输出: True
    解释: 序列中有3个132模式的的子序列: [-1, 3, 2], [-1, 3, 0] 和 [-1, 2, 0].

--------------------

**解法1** 顺序查找  
语言：C

bool find132pattern(int* nums, int numsSize){ 
        if (numsSize < 3) { 
            return false;
        }
        int tmp = nums[0];
        for (int i = 1; i < numsSize; i++) { 
            if (nums[i] > tmp) { 
                for (int j = i + 1; j < numsSize; j++) { 
                    if (nums[i] > nums[j] && nums[j] > tmp) { 
                        return true;
                    }
                }
            } else { 
                tmp = nums[i];
            }
        }
        return false;
    }

时间复杂度： O ( n 2 ) O(n^2) O(n2)  
空间复杂度： O ( 1 ) O(1) O(1)

--------------------

**解法2** 对数组维护前缀最小值+栈（LeetCode官方题解）  
我们首先考虑`a[i] < a[j]`的部分。当我们固定了`j`时，我可以在`j`的左侧找出一个最小的数作为`a[i]`，这是因为最终我们需要满足`a[i] < a[k] < a[j]`，那么`a[i]`一定越小越好。因此我们可以对数组`a`维护前缀最小值，即`min[j] = min(a[1 .. j])`，这样对于一个固定的`j`，`min[j]`即为最优的`a[i]`。  
随后我们再考虑`a[k]`，其中`a[k]`需要满足`a[i] < a[k] < a[j]`，即`min[j] < a[k] < a[j]`。我们可以从数组`a`的末尾开始，从后向前寻找`a[k]`。  
我们可以用栈来存储所有的`a[k]`。在栈中，所有候选的`a[k]`保持降序，即栈顶的元素最小，栈底的元素最大。即如果我们遇到一个新的`a[k]`，那么我们会将栈顶的元素依次出栈，直到新的`a[k]`为栈中的最小元素。我们在从右向左遍历数组`a`时，假设我们当前位于`a[j]`，首先我们判断是否有`nums[j] > min[j]`，如果不成立，那么我们要跳过这个`a[j]`，否则我们将栈顶的元素依次出栈，直到栈顶元素`stack[top]`满足`stack[top] > min[j]`。在这之后，我们可以确定栈中的所有元素都大于`min[j]`（即`nums[i]`），因此如果此时栈顶的元素和`j`可以满足132模式，那么我们就找到了一组合法的满足132模式的`i, j, k`，否则我们继续寻找，此时需要把`a[j]`入栈。  
如果在遍历结束后，我们仍然没有找到满足132模式的`i, j, k`，那么我们需要返回`False`。  
语言：Java

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

时间复杂度： O ( n ) O(n) O(n)  
空间复杂度： O ( n ) O(n) O(n)