[toc]

# 单调栈的性质:

下面这两条很重要

1. 单调栈实际上就是一个栈
2. 每次新元素入栈后，单调栈内元素都保持单调 (递增或递减)

实现起来也很简单，就是标准入栈过程，只需要维护栈内的单调性就可以了 单调栈常用来解决一种典型问题：下一个最大元素

输入一个数组，返回一个等长的数组，对应索引存储着下一个更大的元素，如果没有更大的元素，就存 - 1

Leetcode

# 496,Next Greater Number

这道题 O (N^2) 就可以了
一种优化方法是，在 map 上把 nums2 给装进去，然后遍历 nums1 时二分 map 然后这道题的描述很 shit, 其实这道题说的意思不是相同下标，而是两个数组相同值的右边 就是单调栈模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> nm;
        for(int i=0;i<nums1.size();++i){
            nm[nums1[i]]=i;
        }
        stack<int> st;
        vector<int> n2(nums2.size());
        for(int i=nums2.size()-1;i>=0;--i){
            while(!st.empty() && st.top()<=nums2[i]){
                st.pop();
            }
            n2[i] = st.empty()?-1:st.top();
            st.push(nums2[i]);
            if(nm.count(nums2[i])){
                nums1[nm[nums2[i]]] = n2[i];
            }
        }
        return nums1;
    }
};

# 下一个更大的元素 ②

这道题没规定循环只能到自己为止

这道题本来想做一个 struct, 有下标和数据，然后拓展 vector 到二倍

但是官方题解说可以直接用单调栈只记录下标

确实，这样会省略掉很多麻烦的问题。然后是正向单调栈的方案 上一题用的是逆序插入单调栈，每次遇到的第一个大于当前元素的则一定是对的。正序插入单调栈，我们就需要维护该单调栈仍然是单调递减的，对于 pop 出来的而言，他就是第一个比他们大的。所以要在 pop 的时候赋值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public: 
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        stack<int> st;
        vector<int> dev(nums.size(),-1);
        for(int i=0;i<nums.size()*2-1;++i){
            while(!st.empty() && nums[st.top()]<nums[i%n]){
                dev[st.top()] = nums[i%n];
                st.pop();
            }
            st.push(i%n);
        }
        return dev;
    }
};

# discuss 里的一道面试题

https://leetcode-cn.com/circle/discuss/l8Hse4/ 第 1 题 给定一个长度为 m（m >= 1）的字符串，这个字符串表示一个非负整数 N（应该可以用 long 装下，我是最后超时了）。其中 N 没有前导 0。 再给定一个整数 x（x <= m），要你从整数 N 中删除 x 个数字，使得余下的数字最小。最后输出这个最小的数字。 例如：
输入：N=2020，x = 1
输出：20
解释：删除第一个 2，剩下 020=20 输入：N=1432319，x = 3
输出：1219

先讨论性质 方法一，考虑保留哪些数

1. 考虑保留那些数

方案 1：N 长度为 m，删除 x 个数字，那就剩 m-x 个数字，所以就是求原始序列 N 的长度为 m-x 的子序列，使得这个子序列最小。 以输入 N = 1432319 为例，m=7 x=3，m-x=4，所以我们的目标是要从 N 中挑出 4 个数来，这 4 个数的相对顺序是不能变的。下面是步骤：

1
2
3
4

N=1432319，目标长度4，所以第1个数只能从1432里面取，不然后面的数就不够用了。这里肯定选最小的1，结果变成1
N=432319，目标长度3，所以第2个数只能从4323里面取，不然后面的数不够用了，同理选2，结果变成12
N=319, 目标长度2，所以第3个数只能从31里面取，不然后面的数不够用了，同理选1，结果变成121
N=9，不说了。。。，最终结果变成1219

方案 2：上面的方案中，需要每次去找某个区间的最小值，导致时间复杂度是 O (m*x)，如果想优化可以针对这个问题引入单调 (递增) 栈，单调栈这里就不介绍了，网上随便搜一下就有。具体步骤：

1
2
3
4
5
6

启动的时候先压入4个数1432，压完单调栈变成12
栈底的1出栈，放到结果中，同时1432后面的3压栈，单调栈变成23
栈底的2出栈，放到结果中，同时14323后面的1压栈，单调栈变成1
栈底的1出栈，放到结果中，同时143231后面的9压栈，单调栈变成9
栈底的9出栈，放到结果中
返回最终结果1219

改进后时间复杂度变为 O (m)，但注意这是一个变种栈，我们从栈底而不是栈顶出栈，所以栈的底层实现需要是 linkedlist，而不是 array。 这句话中的那四步非常重要，即考虑剩下 4 个，那么就只能在前面 N-4 个值中取一个最小的放到最高位上 第一位找好了，找第二位，考虑剩下 3 个，就只能在刚才选好的下标后面的子串中 不包含最后三位 中找一个最小的放到最高位上 这个过程可以用单调栈进行区间最小值的查找 这个思路非常巧妙