讲解单调栈

单调栈适用于一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置
单调栈最重要的问题就是，栈内是递增还是递减的？
找大的就是递减，找小的就是递增

变形体0：左侧第一个小的单调栈

题源acwing830
给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int stk[N], tt;
int main(){
	int n;
	cin >> n;
	while(n --){
		int x;
		scanf("%d", &x);
		while(tt && stk[tt] >= x) tt--;//如果栈顶元素大于当前遍历元素，就出栈，tt减到底，并且中间元素都不再需要
		if(!tt) printf("-1");//栈顶指针为0了，当前元素左边没有比他小的值
		else printf("%d ", stk[tt]);//输出栈顶元素，栈顶元素就是左侧第一个比它小的
		//注意这里顺序，先输出答案再更新
		stk[++tt] = x;//更新stk，他还有可能成为答案
	}
	return 0；
}

变形题1：每日温度

题源力扣739

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数

本题是要找右侧第一个比自己大的元素

1. 单调栈里面放什么：这一题应该放元素下标，这样好计算等待天数，直接temperature[i]也可以获得对应的元素
2. 单调栈是递增还是递减(栈底到栈顶)：应该是递减的，找小的递增，找大的递减

我的学习经验是，先想明白栈里放什么和递增递减的问题，然后再从单调栈使用方向去思考什么时候出栈什么时候入栈，是找左侧还是找右侧是区别很大的，这些想要想明白了再去敲

如何使用这个单调栈：

• 当遍历温度数组时，对于每个元素，都会检查栈顶元素索引代表的温度是否小于当前元素的温度
• 如果栈顶元素索引代表的温度小于当前元素的温度，说明已经找到了栈顶元素索引代表的温度右侧第一个大于他的温度，这个时候res[index] = i - stk[s.top()]，栈顶索引的右侧第一个大的温度找到了，所以栈顶需要出栈！
• 如果栈顶元素索引代表的温度并不小于当前元素的温度，说明还没有找到，当前序列是一直递减的，4 3 2 1这样，自然没有右侧第一个大的，所以当前元素的索引入栈

/*
请根据每日气温列表 temperatures ，重新生成一个列表
要求其对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。
如果气温在这之后都不会升高，请在该位置用 0 来代替。
*/
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> stk;
        vector<int> res(temperatures.size(), 0);
        for(int i = temperatures.size() - 1; i >= 0; i --){
            while(!stk.empty() && temperatures[stk.top()] <= temperatures[i]) stk.pop();
            // 如果栈不为空，栈顶元素就是右侧第一个更高的温度
            if (!stk.empty()) {
                res[i] = stk.top() - i; // 计算天数差
            }
            stk.push(i);
        }
        return res;

    }
};

变形题2：下一个更大元素I

力扣496
给你两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

这题和每日温度几乎是一样的，只是绕了一下，需要对单调栈更熟练

1. 因为是nums1在num2中右侧第一个大的元素，所以需要一个和nums1一样长的数组来存结果，并且由于找不到的话输出-1，所以这个结果数组应该初始化全是-1
2. 在遍历nums2的过程中，我们要判断nums2[i]是否在nums1中出现过，因为最后是要根据nums1元素的下标来更新result数组。
3. 注意题目中说是两个没有重复元素的数组 nums1 和 nums2。
4. 没有重复元素，我们就可以用map来做映射了。根据数值快速找到下标，还可以判断nums2[i]是否在nums1中出现过。

预处理：

unordered_map<int, int> umap; // key:下标元素，value：下标
for (int i = 0; i < nums1.size(); i++) {
    umap[nums1[i]] = i;
}

很多题解这里栈也存的索引，其实都可以，毕竟有map了
需要注意的是这里的出栈条件，s.pop()需要放在if语句的外面，需要确保，无论栈顶元素是否在nums1中，都将其从栈中移除，因为栈顶元素的下一个更大的元素已经被找到，只是因为不在nums1中不必被记录

//题目保证不重复了，才可以<而不是<=！！！！！！！！！！！！！！！！！！！！1

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> umap;
        for(int i = 0; i < nums1.size(); i ++) umap[nums1[i]] = i;

        stack<int> stk;
        vector<int> res(nums2.size(), -1);
        vector<int> res1(nums1.size(), -1);
        for(int i = nums2.size() - 1; i >= 0; i --){
            while(!stk.empty() && stk.top() < nums2[i]) stk.pop();//题目保证不重复了，才可以<而不是<=！！！！！！！！！！！！！！！！！！！！1
            if(!stk.empty()) res[i] = stk.top();
            stk.push(nums2[i]);
        }
        //res存的是nums2右侧第一个大的数
        for(int i = 0; i < nums2.size(); i ++){
            if(umap.count(nums2[i]) > 0){
                res1[umap[nums2[i]]] = res[i];
            }
        }
        return res1;
    }
};

变形题3：下一个更大元素II

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

除了循环数组，其他是一样的
如何处理循环数组呢？
可以把两个数组拼起来，然后使用单调栈求下一个最大值！最后再把结果即result数组resize到原数组大小就可以了。
但扩充nums数组相当于多了一个O(n)的操作。这里没有必要扩充
nums[i % nums.size()] 代替 nums[i]

//相等也要pop掉！！！！！！！！！！！！！！！！！！！！
AC代码

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int sz = nums.size();
        nums.resize(sz * 2);
        for(int i = 0, j = sz; i < sz; i ++){
            nums[j] = nums[i];
            j ++;
        }
        //开始找新数组的下一个更大
        stack<int> stk;
        vector<int> res(nums.size(), -1);
        for(int i = nums.size() - 1; i >= 0; i --){
            while(!stk.empty() && stk.top() <= nums[i]) stk.pop();//相等也要pop掉！！！！！！！！！！！！！！！！！！！！
            if(!stk.empty()) res[i] = stk.top();
            stk.push(nums[i]);
        }
        //输出前sz个
        vector<int> res1(sz, -1);
        for(int i = 0; i < sz; i ++){
            res1[i] = res[i];
        }  
        return res1;
    }
};

变形题4：链表中的下一个更大节点

单调栈的很直接

//从右到左遍历，遇到更大的元素时，弹出栈中元素
//因为这些被弹出的元素不可能再作为右侧第一个大的
//所以栈应该是递减
class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) {
        //链表转成数组
        vector<int> nums;
        for(ListNode* p = head; p != nullptr; p = p->next) nums.push_back(p->val);

        int sz = nums.size();
        stack<int> stk;
        vector<int> res(sz, 0);
        for(int i = sz - 1; i >= 0; i --){
            while(!stk.empty() && stk.top() <= nums[i]) stk.pop();
            res[i] = stk.empty() == 1 ? 0 : stk.top();//必须是res[i]，而不是push_back
            stk.push(nums[i]);
        }

        return res;
    }
};

变形题5：接雨水

大厂的热爱
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

这里给三种方法，暴力，双指针优化和单调栈

其实在做到双指针的时候应该就能想到单调栈了
平时单调栈记录的是左右第一个比自己大或小的元素
而接雨水这道题目，我们需要寻找一个元素，右边最大元素以及左边最大元素，来计算雨水面积。

需要两个单调栈来分别记录左边最大和右边最大吗？不用的

1. 首先单调栈是按照行方向来计算雨水的
   

2. 单调栈内元素是递增还是递减呢
   栈底到栈顶，应该是递减的
   因为一旦发现添加的柱子高度大于栈头元素了，此时就出现凹槽了，栈头元素就是凹槽底部的柱子，栈头第二个元素就是凹槽左边的柱子，而添加的元素就是凹槽右边的柱子。
   所以一个栈就解决了一个凹，不需要两个栈！！

3. 遇到相同高度的柱子了怎么办？
   遇到相同的元素，更新栈内下标，就是将栈里元素（旧下标）弹出，将新元素**（新下标）加入栈中。
   因为我们要求宽度的时候如果遇到相同高度的柱子，需要使用最右边的柱子来计算宽度**。实际上这一步并不需要特殊处理

4. 栈里保存什么值，保存下标，毕竟水的面积是长×宽，

/*
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图
计算按此排列的柱子，下雨之后能接多少雨水。
*/
class Solution {
public:
    int trap(vector<int>& height) {
        //有单调栈的思想之后好像很简单(狐疑)
        //找右侧第一个大于等于他的柱子，那么这俩之间就可以接水
        stack<int> stk;
        int area = 0;
        for(int i = height.size() - 1; i >= 0; i --){
            while(!stk.empty() && height[stk.top()] <= height[i]){
                int top = stk.top();
                stk.pop();
                if(stk.empty()) break; // 如果栈中没有其他柱子，说明不能形成洼地
                int distance = stk.top() - i - 1;
                int bounded_height = min(height[stk.top()], height[i]) - height[top];//计算高度差
                area += distance * bounded_height;
            }
            stk.push(i);
        }
        return area;
    }
};

变形题6：柱状图中的最大矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

接雨水是找每根柱子左右两边第一个大于该柱子高度的柱子，而本题是找每个柱子两边第一个小于该柱子高度的柱子
那么单调栈内应该是栈底到栈顶是递增的，遇到小于s.top，则弹出

注意1：
height数组前后需要加上一个元素0，先说为什么结尾加0
为的就是防止height一直升序，假设height数组是[1,2,3,4,5]，就会一直入栈，没有计算sum的机会，假如在末尾添加0就可以正常计算了
开头添加0也是一样的，如果数组本身是降序的，[5,4,3,2,1]，5入栈后，4与5比较，这时得不到left。因为 将 8 弹出之后，栈里没有元素了，那么为了避免空栈取值，直接跳过了计算结果的逻辑。之后又将6 加入栈（此时8已经弹出了），然后 就是 4 与 栈口元素 8 进行比较，周而复始，那么计算的最后结果resutl就是0。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        heights.insert(heights.begin(), 0); // 数组头部加入元素0
        heights.push_back(0); // 数组尾部加入元素0
        st.push(0);
        int result = 0;
        for (int i = 1; i < heights.size(); i++) {
            while (heights[i] < heights[st.top()]) {
                int mid = st.top();
                st.pop();
                int w = i - st.top() - 1;
                int h = heights[mid];
                result = max(result, w * h);
            }
            st.push(i);
        }
        return result;
    }
};

变形题7：最大矩形

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

这道题是后续补充的，为什么放这里呢，因为他和柱子的最大矩形息息相关

思路是将每一行视为柱状图的底部，高度是由每列连续的1数量决定的，然后对于每一行，使用柱状图的最大矩形的解法。

class Solution {
//每一行都当做柱状图的下划线
int largestArea(vector<int> heights){
    stack<int> stk;
    heights.push_back(0);
    heights.insert(heights.begin(), 0);
    stk.push(0);
    
    int res = 0;
    for(int i = 1; i < heights.size(); i ++){
        while(heights[i] < heights[stk.top()]){
            int mid = stk.top();
            stk.pop();
            int h = heights[mid];
            int w = i - stk.top() - 1;
            res = max(res, h * w);
        }
        stk.push(i);
    }
    return res;
}
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<int> heights(cols, 0);

        int maxArea = 0;
        for(int i = 0; i < rows; i ++){
            for(int j = 0; j < cols; j ++){
                heights[j] = (matrix[i][j] == '1') ? heights[j] + 1 : 0;
            }
            maxArea = max(maxArea, largestArea(heights));
        }
        return maxArea; 
    }
};

单调队列

变形题0：滑动窗口

经典滑动窗口
又名单调队列的实现
题目：给定一个大小为n <= 10^6 的数组。有一个大小为k的滑动窗口，它从数组的最左边移动到最右边，你只能在窗口中看到k个数字，每次滑动窗口向右移动一个位置。
以下是一个例子[1，3，-1，-3，5，3，6，7]，k为3

任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

由于需要求出滑动窗口的最大值：

• 如果nums[i] <= nums[j]，当滑动窗口移动的时候，只要 i 还在窗口内，那么 j 就一定还在窗口内，所以由于nums[j]的存在，nums[i]一定不会是滑动窗口的最大值！！！我们可以将nums[i]永久的删除
• 用一个队列存储所有还没有被移除的下标。在队列中，这些下标按照从小到大的顺序被存储。并且它们在数组nums中对应的值是严格单调递减的。
• 滑动窗口右移的时候，把一个新元素放入队列。不断地将新的元素与队尾的元素相比较，如果新元素大于等于队尾元素，那么队尾的元素就可以被永久地移除，我们将其弹出队列。我们需要不断地进行此项操作，直到队列为空或者新的元素小于队尾的元素。
• 由于队列中下标对应的元素是严格单调递减的，因此此时队首下标对应的元素就是滑动窗口中的最大值。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
using namespace std;
const int N = 1e6+10;
int a[N];
int main(){
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i ++ ) cin >> a[i];//读入数据
	deque<int> q;
	//求最小值
	for(int i = 1; i <= n; i ++){
		while(q.size() && q.back() > a[i]) q.pop_back();//新进入窗口的值小于队尾元素,则队尾出队列
		q.push_back(a[i]);
		if(i - k >= 1 && q.front() == a[i - k]) q.pop_front();
		if(i >= k) cout << q.front() << " ";
	}
	q.clear();
	cout << endl;
	//求最大值
	for(int i = 1; i <= n; i ++){
		while(q.size() && q.back() < a[i]) q.pop_back();
		q.push_back(a[i]);
		if(i - k >= 1 && q.front() == a[i - k]) q.pop_front();
		if(i >= k) cout << q.front() << " ";
	}
}