[LeetCode]132 Pattern

假设我们从左向右遍历，每找到一个符合条件的pair(a, b)，a < b，之后我们如果碰到在(a, b)范围内的数就说明我们找到了符合条件的pattern。但问题是我们可能有多个这样的pair，这样符合要求的区间也可能有多个，这样让我们并不好判断当前数是否符合条件。如果换一种思维，从右向左依次遍历的话，我们可以发现可以简单很多，对于处在i位置的数nums[i]，如果存在j > i的数满足nums[i] > nums[j]，我们只需要判断在[i + 1, len - 1]区间里，小于nums[i]的最大数c是什么即可，以后如果我们遇到小于c的数就说明我们找到了这样一个pattern。那么我们将这道题转化为对于nums[i]我们如何求出[i + 1, len - 1]小于nums[i]的最大数c。很显然，如果用我们熟知的数据结构，BST可以帮我们做到这一点，时间复杂度为O(n * log n)。但是这里还是依然有重复的计算，假设我们在遍历到b的时候找到了c，我们遇到了一个比b更大的数x，那么我们需要去更新c，因为x的存在可能可以让c变得更大，这样我们找132pattern的第一个数的限制条件会更宽松。那么这一次更新的过程，我们完全就不需要考虑之前在b已经排除的数字了。如果我们用stack维护一个从右向左的递减序列，每当我们碰到了比栈顶更大的数curr，我们pop直到我们得到比curr小的最大值，那么我们就得到了c，同时排除了所有我们之后不需要考虑的数，我们继续插入curr继续之前的步骤，直到我们找到pattern或者发现不存在pattern。这样的话，每个数最多只会在栈上进出一次，时间复杂度O(n)，空间复杂度O(n)，代码如下：

	class Solution {
	public:
	bool find132pattern(vector<int>& nums) {
	int len = nums.size(), lo = INT_MIN;
	stack<int> st;
	for(int i = len - 1; i >= 0; --i)
	{
	int curr = nums[i];
	if(curr < lo)return true;
	while(st.size() && st.top() < curr)
	{
	lo = st.top();
	st.pop();
	}
	st.push(curr);
	}
	return false;
	}
	};

view raw 132 Pattern.cpp hosted with ❤ by GitHub

值得一提的是，维护单调序列来避免重复计算的思路在很多题当中都有出现。比如: Largest Rectangle in Histogram,  Sliding Window Maximum