830 单调栈

https://www.acwing.com/problem/content/description/832/

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
/*
乍一看这道题可以使用双指针/滑动窗口，但实际上双指针是对指针的边界进行移动，以此达到On的复杂度
而这道题里，一旦向右移动时，左侧指针也会跟着变化，所以双指针实现等同于两层循环遍历

所以维护一个栈保存局部最小值，有点像水池一边放水一边进水，参考系是扫描元素和栈顶元素
根据条件只能入栈比当前扫描元素小的值，否则将其出栈(while，有可能要出栈好多个)，所以单调栈是单调递增的

单调栈所维护的对象可以是数组元素或数组下标，而滑动窗口的“栈”必须是数组下标，需要用下标维护窗口
*/
const int N = 1e5 + 10;
int stk[N]; // 单调栈
int tail;   // 栈的头结点指针

int main()
{
    int n; cin >> n;

    for (int i = 0; i < n; i++)
    {
        int tmp; cin >> tmp;

        while (tail && stk[tail] >= tmp)  // while
            tail--;

        if (tail)
            cout << stk[tail] << ' ';  // 如果不空说明有符合的值
        else
            cout << -1 << ' ';  // 如果栈空输出-1

        stk[++tail] = tmp;
    }
    return 0;
}

41 包含min函数的栈

https://www.acwing.com/activity/content/code/content/3324625/

131 直方图中最大的矩形

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
/*
这道题的思路是：
    根据每个数组的高度枚举所有可能产生的面积，然后更新最大值

如何确定面积的宽高？
    高度是已知的，阴影面积的高度必然是已存在的某个高度，枚举就好
    宽度需要考虑已确定高度的左右，如果左右比当前高度高，可用，如果低，不可用

所以可以将问题转化为：
    枚举每一种高度，然后使用单调栈确定该高度左右的最大高度，再更新宽度

为什么不使用双指针？(将信将疑)
    因为每次枚举不同高度时，当前双指针结果不一定可用，没有降低时间复杂度
    而且很明显，需要快速得出左右的最大高度进行判断，所以肯定是单调栈
*/
const int N = 1e5 + 10;
int h[N];  // 高度数组
int l[N], r[N];  // 单调栈，分别记录左右的元素下标
int q[N];  // 辅助单调栈的数组，没啥用

int main()
{
    int n;
    while (cin >> n, n)
    {
        for (int i = 1; i <= n; i++)
            cin >> h[i];

        h[0] = h[n + 1] = -1;  // 边界初始化为-1，防止影响答案面积

        int tail = 0;  // 单调栈顶，初始化为0，实际元素从1开始
        q[0] = 0;

        for (int i = 1; i <= n; i++)  // 根据高度数组从左向右更新单调栈
        {
            while (h[q[tail]] >= h[i])  // 如果当前元素大于单调栈顶元素，入栈，否则出栈
                tail--;

            l[i] = q[tail];  // i位置时左面第一个比他小的元素下标
            q[++tail] = i;  // 约等于入栈
        }

        tail = 0;
        q[0] = n + 1;  // 初始化到右边，更新单调栈

        for (int i = n; i; i--)
        {
            while (h[q[tail]] >= h[i])
                tail--;

            r[i] = q[tail];
            q[++tail] = i;
        }

        long long res = 0;
        for (int i = 1; i <= n; i++)
        {
            long long sum = (long long)h[i] * (r[i] - l[i] - 1);  // 枚举面积
            res = max(res, sum);
        }
        cout << res << endl;
    }
    return 0;
}

4279 笛卡尔树

https://www.acwing.com/problem/content/description/4282/

方法1 dfs记录层数并输出

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
/*
笛卡尔树的特征就是中心遍历为原始序列
所以最小值就是根结点，可以依次对左右递归

该题使用一个vector数组记录每一层的结点
比较好奇的是这道题真的用到单调栈思想了吗？？？
*/
const int N = 40;
int w[N];               // 元素数组
vector<int> level[N];   // 层序遍历数组

int getmin(int l, int r)  // 返回当前区间最小值，这也不算单调栈啊
{
    int res = l;
    for (int i = l; i <= r; i++)
        if (w[res] > w[i])
            res = i;
    return res;
}

void dfs(int l, int r, int d)
{
    if (l > r)
        return;

    int root = getmin(l, r);        // 区域内最小值就是根节点
    level[d].push_back(w[root]);    // 第d层存入节点root

    dfs(l, root - 1, d + 1);
    dfs(root + 1, r, d + 1);  // 递归左右子树
}

int main()
{
    int n; cin >> n;
    for (int i = 0; i < n; i++)
        cin >> w[i];

    dfs(0, n - 1, 0);  // 区间，第0个位置

    for (int i = 0; level[i].size(); i++)  // 按层打印
        for (auto c : level[i])
            cout << c << ' ';

    return 0;
}

方法2 dfs查找+bfs输出

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
/*
先dfs记录每个节点的左右子树，下标更新到L[]R[]
再bfs还原每一层可能存在的左右节点

递归没太看懂
*/
const int N = 40;
int w[N];       // 元素数组
int L[N], R[N]; // 存储idx节点的左右子树下标
int q[N];       // bfs队列

int getmin(int l, int r)
{
    int res = l;
    for (int i = l; i <= r; i++)
        if (w[res] > w[i])
            res = i;

    return res;
}

int dfs(int l, int r)  // 类似折半查找的方法，对数组进行递归
{
    if (l > r)
        return -1;  // 空节点

    int root = getmin(l, r);  // 区域内最小值就是根节点

    L[root] = dfs(l, root - 1);
    R[root] = dfs(root + 1, r);  // 递归左右子树

    return root;  // 根节点的左右子树节点下标
}

void bfs(int root)
{
    int head = 0, tail = 0;
    q[0] = root;  // 入队

    while (head <= tail)
    {
        int tmp = q[head++];  // 下标出队
        cout << w[tmp] << ' ';

        if (L[tmp] != -1)
            q[++tail] = L[tmp];
        if (R[tmp] != -1)
            q[++tail] = R[tmp];  // 如果tmp的左右子树不是空节点，则入队
    }
}

int main()
{
    int n; cin >> n;
    for (int i = 0; i < n; i++)
        cin >> w[i];

    int root = dfs(0, n - 1);
    bfs(root);

    return 0;
}

152 城市游戏

https://www.acwing.com/problem/content/description/154/
救命

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
/*
救命
*/
const int N = 1010;
char g[N][N];   // 原二维数组
int h[N][N];    // 记录xy点的高度
int l[N], r[N]; // 存储左右列可扩展的宽度
int q[N];       // 单调栈
int n, m;

void get(int a[], int left[])
{
    int tail = 0;
    q[0] = 0;
    a[0] = -1;

    for (int i = 1; i <= m; i++)
    {
        while (a[q[tail]] >= a[i])  // 单调递增，否则出栈
            tail--;

        left[i] = q[tail] + 1;
        q[++tail] = i;
    }
}

int func(int a[])
{
    get(a, l);
    reverse(a + 1, a + 1 + m);
    get(a, r);
    reverse(a + 1, a + 1 + m);  // 因为从1起，所以a+1

    int res = 0;

    for (int i = 1; i <= m; i++)
    {
        int left = l[i];
        int right = m + 1 - r[m + 1 - i];  // 因为上面进行了二次翻转，所以要二次还原

        res = max(res, a[i] * (right - left + 1));
    }
    return res;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            char tmp; cin >> tmp;
            g[i][j] = tmp;

            if (tmp == 'F')
                h[i][j] = h[i - 1][j] + 1;
            else
                h[i][j] = 0;
            // dp思想，累计第j列中每个位置的状态
            // 比如000就说明三个位置都不是F，1201230说明两个部分都是F，长度为2和3
        }

    int res = 0;
    for (int i = 1; i <= n; i++)
        res = max(res, func(h[i]));

    cout << res * 3;
    return 0;
}

力扣496 下一个更大元素

https://leetcode.cn/problems/next-greater-element-i/

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> stk;
        unordered_map<int, int> hash;  // 使用哈希存储当前点与左面更小点的对应关系<元素，对应右面更大值>

        for (int i = nums2.size() - 1; i >= 0; i--)
        {
            while (stk.size() && stk.top() <= nums2[i])  // 在使用top()时，要先判断栈空！
                stk.pop();

            hash[nums2[i]] = stk.empty() ? -1 : stk.top();  // 先记录之前的最大，再入栈
            stk.push(nums2[i]);  // 因为入栈的就是当前元素
        }

        vector<int> res(nums1.size());
        for (int i = 0; i < nums1.size(); i++)
            res[i] = hash[nums1[i]];

        return res;
    }
};

力扣503 下一个更大元素2

https://leetcode.cn/problems/next-greater-element-ii/

/*
找右面第一个比自己小的，所以nums[stk.top()]一定是小于nums[i]
单调栈存储的是单调递减的元素下标，然后在res中存储大的元素
注意因为打了双圈，所以要加取余nums[i%n]
*/
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> res(nums.size(), -1);
        if (!nums.size())
            return res;

        stack<int> stk;  // 存储下标
        int n = nums.size();

        for (int i = 0; i < 2 * n; i++)  // 递归两次数组
        {
            while (!stk.empty() && nums[stk.top()] < nums[i % n])
            {
                res[stk.top()] = nums[i % n];  // 栈顶元素更新为第一个比自己大的
                stk.pop();
            }

            stk.push(nums[i]);
        }
        return res;
    }
};

力扣739 每日温度

https://leetcode.cn/problems/daily-temperatures/

/*
找每个位置右面第一个比自己大的数的下标，然后j-i
注意不同的单调栈问题对栈的处理也不一样，比如y总就是在栈里操作更新
    而力扣大多数只拿栈当做下标用，然后在res里更新

单调栈有两种思路：这里是第一种
找下一个：反向遍历
如果要找下一个大的元素——递减栈，栈顶小的没用，出栈
如果要找下一个小的元素——递增栈，栈顶大的没用，出栈

找上一个：正向遍历
如果要找上一个大的元素&&小的元素——思路方法同上
找大去小，找小去大

还要搞清楚是在入栈还是出栈的节点对res操作
*/
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& nums) {
        vector<int> res(nums.size(), 0);
        if (!nums.size())
            return res;

        stack<int> stk;

        for (int i = nums.size() - 1; i >= 0; i--)
        {
            while (!stk.empty() && nums[stk.top()] <= nums[i])  // 注意是否有等于
                stk.pop();  // 出栈时不操作的

            res[i] = stk.empty() ? 0 : stk.top() - i;  // 一般来讲如果在入栈位置操作，则需要加empty判断
            stk.push(i);
        }
        return res;
    }
};

/*
第二种方法是正向递归，然后在某个节点更新res

判断top()和i是否有等于号的问题，需要根据是正向还是反向遍历以及条件决定
*/
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& nums) {
        vector<int> res(nums.size(), 0);
        if (!nums.size())
            return res;

        stack<int> stk;

        for (int i = 0; i < nums.size(); i++)
        {
            while (!stk.empty() && nums[stk.top()] < nums[i])  // 注意没有等于
            {
                res[stk.top()] = i - stk.top();
                stk.pop();
            }

            stk.push(i);
        }
        return res;
    }
};