单调栈Leetcode （持续更新中2022.10.04）

单调栈模板1

 void monoStack(vector<int> arr){
    stack<int> stk;  
    for(int i = 0; i < arr.size(); i++){  
        // 单调递增的栈；如果是stk.size() < arr[i]就是单调递减栈  
        while(stk.size() && arr[stk.size()] > arr[i]){  
            // 一些操作  
            stk.pop();  
        }  
        stk.push(i);  
        // 一些操作  
    }  
    // 如果对剩下的元素需要处理的话可以把整个栈弹空  
 }

题目

1. 123 Pattern

题目链接：456.123Pattern
思路：这题是判断给定数组中是否存在a[i] < a[k]且a[k] < a[j]（i < j < k）。这题的精髓就是从后向前遍历，并且维持一个单调栈。

如果下一个需要遍历的元素如上图所示，那么他的右侧就已经满足题目中对于a[j]和a[k]的要求。这时候红色的点就是一个可能的a[j]， 而栈中小于这个红点的最大元素绿点，就是一个可能的a[k]， 我们的目标就是记住最大的可能a[k]，然后判断前面是否有元素比这个最大的可能a[k]小，如果有那我们就存在132pattern，如果不存在那就return false。
代码

bool find132pattern(vector<int>& nums) {
    int n = nums.size(), right = INT_MIN;
    stack<int> stk;
    for(int i = n-1; i>=0; i--){
        if(nums[i] < right) return true;
        while(!stk.empty() && nums[stk.top()] < nums[i]){
            right = max(right, nums[stk.top()]);
            stk.pop();
        }
        stk.push(i);
    }
    return false;
}