面试题｜【面试好题】2. 132模式
FennelDumplings
1070
2021.07.26
发布于 未知归属地
栈C++面试题求职面试

这是面试好题系列的第二篇文章，这个系列的文章主要是基于我最近面试实习生应届生和3年以下工龄的工程师的经验，推荐一些 leetcode 上适合面试的题。在第一篇文章 面试题｜【面试好题】1. 重排链表 中，我们提到了好的面试题要满足几个条件，这里复习一下。

以下几个要点中 (1)(2)(5)必须满足，(3)(4)至少满足一个：
(1) 考查基础的数据结构和主流算法，避开邪门算法和脑筋急转弯
(2) 暴力方法很容易想到
(3) 最好有两种以上的优化方式
(4) 最好有两三道递进的题可以放到一起
(5) 最终代码不长

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

下面我们来看一下这个题

$1 题目

题目链接

给定一个整数序列：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].

题解

算法 : 单调栈

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

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

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

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

代码(c++)

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 模式的应用

题目链接

剑指 Offer 33. 二叉搜索树的后序遍历序列

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

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

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

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

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

代码(C++)

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;
    }
};
评论 (0)