456.md

【中规中矩】456. 132 模式（暴力及单调栈解法）

解题思路

解法1：暴力二重循环，查找nums[k] > ival && nums[k] < nums[j]即可。则ival 是1，nums[k]是2，nums[j]是3。O(N^2)时间。

解法2：单调栈优化。O(N)时间。

代码

// slight better than brute force O(N^2) time, and O(1) space
class Solution1 {
public:
    bool find132pattern(vector<int>& nums) {
        if (nums.size() < 3)
            return false;
        
        int ival = numeric_limits<int>::max();
        int N = nums.size();
        for (int j = 0; j < N - 1; j++) {
            ival = min(ival, nums[j]);
            for (int k = j + 1; k < N; k++) {
                if (nums[k] > ival && nums[k] < nums[j])
                    return true;
            }
        }
        
        return false;   
    }
};

// Even better than solution 1, but still O(N^2) worst case, best case O(N)
class Solution2 {
public:
    bool find132pattern(vector<int>& nums) {
        if (nums.size() < 3)
            return false;
        
        int min_i = 0;
        vector<pair<int, int> > intervals;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] < nums[i - 1]) { // i - 1 is the local maximum
                if (min_i < i - 1)
                    // make a local increasing interval
                    intervals.push_back(make_pair(nums[min_i], nums[i - 1]));
                min_i = i;
            }
            
            // treat the current element as a[k] to check for 132 pattern
            for (auto& interval : intervals)
                if (nums[i] > interval.first && nums[i] < interval.second)
                    return true;
        }
        
        return false;
    }
};

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        if (nums.size() < 3)
            return false;
        
        vector<int> mins;
        auto curMin = numeric_limits<int>::max();
        for (auto& num : nums) {
            curMin = min(curMin, num);
            mins.push_back(curMin);
        }
        
        stack<int> stk;
        auto N = nums.size();
        for (int j = N - 1; j >= 0; j--) {
            if (nums[j] > mins[j]) { // a[i] < a[j]
                while (!stk.empty() && stk.top() <= mins[j]) // a[k] > a[i]
                    stk.pop();
                if (!stk.empty() && stk.top() < nums[j]) // a[k] < a[j]
                    return true;
                stk.push(nums[j]);
            }
        }
        return false;
    }
};

class Solution1(object):
    def find132pattern(self, nums):
        if (len(nums) < 3):
            return False
        
        ival = float('inf')
        N = len(nums)
        for j in range(0, N - 1):
            ival = min(ival, nums[j])
            for k in range(j + 1, N):
                if (nums[k] > ival and nums[k] < nums[j]):
                    return True
        
        return False

class Solution2(object):
    def find132pattern(self, nums):
        if (len(nums) < 3):
            return False
        
        mins = []
        curMin = float('inf')
        for num in nums:
            curMin = min(curMin, num)
            mins.append(curMin)
        
        stk = []
        N = len(nums)
        for j in range(N - 1, -1, -1):
            if (nums[j] > mins[j]): # a[i] < a[j]
                while(stk and stk[-1] <= mins[j]): # a[k] > a[i]
                    stk.pop()
                if (stk and stk[-1] < nums[j]): # a[k] < a[j]
                    return True
                stk.append(nums[j])       

        return False

点我赞赏作者

github 题解