LeetCode 456: “132” Pattern

这个题是昨晚上回寝室前赶出来的，因为看到是Medium而且感觉不难（实际也不难）。

原题：https://leetcode.com/problems/132-pattern

题目意思是，判断一个数组是否包含子序列a_i、a_j、a_k（i<j<k），满足a_i<a_k<a_j。

主算法

思路是遍历每一个可能的k值，然后找到它之前第一个（也就是距离最近的）比它大的数作为a_j，然后再判断a₀~a_j-1之间的最小值是否小于a_k。

之所以要找到“第一个”比它大的数，理由也很明显：要尽量扩大找a_i的范围，否则可能会有false negative的情况。

思路很简单，关键是如何做到O(n)。因为遍历每一个k的过程就是O(n)的，所以要求后面两个步骤都是O(1)，也就是要预处理。预处理最小值很简单，开一个数组记录一下即可，空间复杂度O(n)。预处理“之前第一个比a_k大的数（的位置）”就比较麻烦了，放在子算法里说，空间复杂度也是O(n)。

因此最终算法分三步：预处理a₀~a_j的最小值，预处理a_k之前第一个大的数，遍历每一个可能的k。

子算法

要预处理每个数之前第一个比它大的数，用到了之前一个stack的奇技淫巧。方法是维护一个pair<数, 位置>的stack，其中数是递减的；对于数组从头到尾遍历，每个数先将栈顶比它小的数pop出去，如果pop完了栈空了，说明前面没有比它大的数，此时预处理结果为-1；否则预处理结果为栈顶数的位置。处理完之后将当前pair<数, 位置>也push进栈。

原理：因为要找到之前第一个比它大的数，如果栈顶的数比当前数还小，那对于它们之后的数来说，当前数更可能是比后面数大的结果，所以将栈顶pop出去。因为每个数最多进出栈一次，时间复杂度O(n)。

C++代码

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        if (nums.empty()) return false;
        int n = nums.size();
        vector<int> min1(n);
        min1[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            min1[i] = min(min1[i-1], nums[i]);
        }
        typedef pair<int, int> pii;
        stack<pii> s;
        vector<int> max1;
        for (int i = 0; i < n; ++i) {
            int I = nums[i];
            while (!s.empty() && s.top().first <= I) s.pop();
            if (s.empty()) {
                max1.push_back(-1);
            } else {
                max1.push_back(s.top().second);
            }
            s.push(make_pair(I, i));
        }
        for (int i = n-1; i >= 0; --i) {
            int I = nums[i];
            int j = max1[i];
            if (j == -1 || j == 0) continue;
            if (min1[j-1] < I) return true;
        }
        return false;
    }
};

因为写的很赶，好多边界都没care，其实应该还有能优化的地方（因为运行时间才到beat 55%的位置……）