456.132模式

发表于 | 分类于
字数统计: 481 | 阅读时长 ≈ 2

一、题目描述

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

注意：n 的值小于15000。

示例1:

1
2
3
4
5
输入: [1, 2, 3, 4]

输出: False

解释: 序列中不存在132模式的子序列。

示例 2:

1
2
3
4
5
输入: [3, 1, 4, 2]

输出: True

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

示例 3:

1
2
3
4
5
输入: [-1, 3, 2, 0]

输出: True

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

二、题解

1.算法描述

  • 栈的应用

2.个人分析

参考官解

  1. 为了便于分析，我们约定：
    • “1”：小
    • “3”：大
    • “2”：中
  2. 首先考虑小 < 大的情况，我们可以维护一个前缀最小值的数组min[]，这样，小 < 大便是最优解
  3. 其次考虑大 > 中的情况，我们需要申请一个栈，从后向前遍历数组，
    1. 当nums[j] > min[j]时，将nums[j]进栈
    2. 如果栈不为空，并且nums[j] > stack[top]时，我们就找到了我们需要的中，返回true；
    3. 如果栈不为空，但是min[j] >= stack[top]时，我们就需要一直出栈，直到找到我们所需要的中
  4. 如果遍历完整个数组，都没有找到，则返回false

3.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
bool find132pattern(int *nums, int numsSize)
{
    if (numsSize < 3)
        return false;
    //min[]
    int min[numsSize];
    min[0] = nums[0];
    int i, j;
    for (i = 1; i < numsSize; i++)
        min[i] = min[i - 1] < nums[i] ? min[i - 1] : nums[i];

    int stack[numsSize];
    int top = -1;

    for (j = numsSize - 1; j >= 0; j--)
    {
        if (nums[j] > min[j])
        {
            while (top != -1 && min[j] >= stack[top])
                top--;
            if (top != -1 && nums[j] > stack[top])
                return true;
            stack[++top] = nums[j];
        }
    }
    return false;
}