算法leetcode

力扣456-132模式

字数统计: 1.2k字   |   阅读时长: 5分
,

摘要: 用单调栈解决 132 模式问题，132 模式可以作为组件解决其他问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 面试好题 中，我提到了我认为的适合作为面试题的标准，这里复习一下：

对于适合面试的题目，以下几个要点中 (1)(2)(5)必须满足，(3)(4)至少满足一个：

(1) 考查基础的数据结构和主流算法，避开邪门算法和脑筋急转弯

(2) 暴力方法很容易想到

(3) 最好有两种以上的优化方式

(4) 最好有两三道递进的题可以放到一起

(5) 最终代码不长

今天我们看一个比较适合面试的题，leetcode第456题，132模式。本题考察的是单调栈，属于基础算法，暴力方法也很容易想到，代码也短，因此 (1)(2)(5) 是满足的。在此基础上，本题作为组件可以用于解决很多问题。也就是说，很多题在经过抽象之后，都可以用 132 模式的思路解决，因此本题也满足 (4) 这个条件。

下面我们来看一下这个题。

$1 题目：132 模式

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

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

提示：

1
2
3
n == nums.length
1 <= n <= 2 * 1e5
-1e9 <= nums[i] <= 1e9

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

算法：单调栈

从后往前枚举，维护一个次大值 sub_maxx 以及一个单调栈 st。栈是单调不增的。

当前值为 cur，如果 cur < sub_maxx 返回 true;

如果 cur >= sub_maxx，则 st 要进栈。在进栈之前，要将栈顶小于 cur 的值弹出，弹出时可能会更新 sub_maxx

1
sub_maxx = max(sub_maxx, st.top());

代码(c++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int n = nums.size();
        if(n < 3) return false;
        stack<int> st;
        int sub_maxx = INT_MIN;
        for(int i = n - 1; i >= 0; --i)
        {
            if(nums[i] < sub_maxx) return true;
            while(!st.empty() && st.top() < nums[i])
            {
                sub_maxx = max(sub_maxx, st.top());
                st.pop();
            }
            st.push(nums[i]);
        }
        return false;
    }
};

$2 132 模式的应用

在 leetcode 中，可以抽象成 132 模式的题有以下几道：

题目 抽象
255. 验证前序遍历序列二叉搜索树 验证前序遍历序列不含231模式
946. 验证栈序列 验证弹出序列不含 312 模式
剑指 Offer 31. 栈的压入、弹出序列 验证弹出序列不含 312 模式
剑指 Offer 33. 二叉搜索树的后序遍历序列 验证后续遍历序列不含 312 模式

以下面这个题为例：

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

提示：

1
数组长度 <= 1000

参考以下这颗二叉搜索树：
5
/ \
2 6
/ \
1 3
示例 1：

输入: [1,6,3,2,5]
输出: false
示例 2：

输入: [1,3,2,6,5]
输出: true

算法：抽象为 132 模式

对本题，通过画图和分析可以得到以下事实：二叉搜索树的后序遍历序列若要合法，它的后序遍历序列中不能有 312 模式，312 模式与 132 模式的做法类似。

从右往左枚举元素，维护次小值 sub_minx，和一个单调栈 st，st 是单调不增的。

当前值为 cur，如果 cur > sub_minx 则找到了 312 模式;

如果 cur <= sub_maxx，则 st 要进栈。在进栈之前，要将栈顶大于 cur 的值弹出，弹出时可能会更新 sub_minx

1
sub_minx = min(sub_minx, st.top());

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        // 不能有 312 模式
        int n = postorder.size();
        if(n <= 2) return true;
        int sub_minx = INT_MAX;
        stack<int> st;
        for(int i = n - 1; i >= 0; --i)
        {
            if(postorder[i] > sub_minx)
                return false;
            while(!st.empty() && st.top() > postorder[i])
            {
                sub_minx = min(sub_minx, st.top());
                st.pop();
            }
            st.push(postorder[i]);
        }
        return true;
    }
};
Share