原题链接

leetcode 456

思路

乍一看题目，以为是楼兰图腾，树状数组的裸题，但是仔细一看（一看就看了一个小时），发现其实没有那么简单。

不过所有看起来不简单的题目都是从简单的分析开始的。

最朴素的想法是枚举，枚举的对象应该是或者。

对枚举

如果对枚举，那么显然我们需要求出两个集合：

  1. 在左侧的最小元素集合；
  2. 在右侧的最大元素（并且不超过它）集合。

前者只需要一次简单的遍历即可完成，而后者需要使用一些trick。最简单的方式是直接遍历一遍右侧，找出不大于其的最大元素；仔细思考，我们可以维护右侧的最大值集合（第一种情况实际上维护了一个只有一个元素的集合，因为没有范围限制），对于每一个，我们只需要在这个集合中找出解即可。

问题来了，什么数据结构？平衡树显然可以胜任，但是维护这个结构需要对数时间复杂度；一个更好的方案是使用一个单调栈。这并不是一个显然的结论，你很容易想到，如果维护一个单调递减的单调栈，那么对于某些元素，其可能因为之前一些元素的入栈，而丢失掉一些可能的解。但是，如果你仔细思考，你会发现，如果这样的元素是满足要求的，那么其之前的元素一定也是满足要求的，因为他们的最小元素集合更大。

故而，第一种思路就是：求出两个集合，比较右侧最大元素是否大于左侧最小元素（注意，此处暗含了当前元素大于左侧最小元素的比较）。

对枚举

如果你觉得第一种方案有一点点绕人，那么我建议你也不要看第二种方案了，因为它更简单，更绕人。

对于而言，我们应该从右往左遍历，因为需要解空间就是其左侧的元素。我们应该维护的是位置元素的集合，并且保证当前的最大应该是小于其中每一个元素的。这样的好处是什么呢？任何时刻，我们只要发现当前遍历的元素小于最大的的值，就说明存在一个合法的以及！（所以在一开始应该将最大的初始化为最小值）。

如何维护？我们维护一个当前最大值以及一个单调栈（单调递减）。单调栈中一开始只有最后一个元素，当前最大值一开始为最小值（下面称最小值）。

  1. 如果当前元素小于最小值，那么已经找到了一个解（当前元素是位置）；
  2. 如果当前的栈顶元素小于当前元素，那么按照单调栈方式维护，并更新最小值（当前元素是位置），而被弹出的元素是位置。

实现

此处给出第二种方法的实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        if(nums.size()<3)return false;
        stack<int> st;
        int maxVal = INT_MIN;
    
        st.push(nums[nums.size()-1]);
        for(int i= nums.size()-2;i>=0;i--){
            if(nums[i]<maxVal)return true;

            while(st.size() && st.top()<nums[i]){
                maxVal = max(maxVal, st.top());
                st.pop();
            }

            if(nums[i]> maxVal){
                st.push(nums[i]);
            }
        }

        return false;
    }
};

// [1,4,0,-1,-2,-3,-1,-2]