Leetcode | 第6节：栈与队列

大家好！这一节我们介绍一些栈与队列相关的问题。这一些问题多半都有一些技巧（比方说时常使用的单调栈等），但也不是完全没有套路。

那么我们开始吧。

数据结构4-5：栈与队列

简单介绍一下栈（Stack）与队列（Queue）。栈就是先进后出（FILO）的数据结构，队列就是先进先出（FIFO）的数据结构。因此如果不配合题目，其实大家也不会觉得栈与队列有什么特别。但配合了具体的Leetcode习题，大家自然也就明白了。

那么我们开始吧。

Problem 1: Leetcode 225 请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。 实现 MyStack 类： void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。 注意： 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。你所使用的语言也许不支持队列。你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

用队列实现栈是一个《算法与数据结构》中的必考题，因此相信你也可以猜到，下一个题目就是用栈来实现队列。

常见的做法是使用两个队列来操作，简单来说，我们准备两个队列queue1, queue2，那么加入一开始只有一个元素，不妨就把它放到queue1里。那么放入第二个元素的时候，怎么调整呢？

事实上，注意到，一开始放入queue1之后，这个元素就一定是“先输出”的（因为我们是在借助队列）。所以再加入的时候，就需要把这个“先输出”的元素给去掉，因此可以把它pop出来，然后放到queue2里面，这样的话，第二个元素放入queue1的时候，就一定是先输出的了，这个时候再把queue2里面的元素放到queue1里面，两个元素的顺序就颠倒了过来，也就完成了我们的目的。

读者可以再思考一下第三，第四个元素放入的时候怎么办？其实也是类似的，比方说对于第三个元素，我们可以先pop掉queue1中的之前的两个元素并同时放到queue2中（这并不会改变一开始元素的顺序），然后把新的元素放入queue1，然后再把queue2中的元素按顺序放回queue1。读者可以自己验证，这样的话得到的队列的顺序一定是我们想要的。

好的，说的算比较明白了，我们看一下代码吧。

queue<int> queue1;
queue<int> queue2;

MyStack() {

}

void push(int x) {
    queue2.push(x);
    while (!queue1.empty()) {
        queue2.push(queue1.front());
        queue1.pop();
    }
    swap(queue1, queue2);
}

int pop() {
    int r = queue1.front();
    queue1.pop();
    return r;
}

int top() {
    int r = queue1.front();
    return r;
}

bool empty() {
    return queue1.empty();
}

这里的pop，top和empty方法我们没有多说，因为你只需要把队列中的top元素处理一下就可以了。

那么这一个问题可不可以用一个队列呢？答案也是可以的，因为我们只要保证每一次新加进来的元素都位于最先输出的位置，就能够满足栈的要求。对于这一个问题，操作就是这样的。

对于每一个新入队列的元素，先加入（保证它在输出的第一位），然后把它之前的所有元素都排出，再按顺序进入队列即可。

读者可以自己验证这个方法的准确性，我们也给出代码。

void push(int x) {
  int n = q.size();
  q.push(x);
  for (int i = 0; i < n; i++) {
    q.push(q.front());
    q.pop();
  }
}

int pop() {
  int r = q.front();
  q.pop();
  return r;
}

/** Get the top element. */
int top() {
  int r = q.front();
  return r;
}

/** Returns whether the stack is empty. */
bool empty() {
  return q.empty();
}

Problem 2: Leetcode 232 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）： 实现 MyQueue 类： void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty() 如果队列为空，返回 true ；否则，返回 false 说明： 你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

这是Problem 1的反问题，但这一个题难度要稍微大一些，我们考虑一下怎么做。

这里我们也是考虑使用两个栈来求解。区分于队列，栈是先进后出的，因此每做一次栈的操作都会改变元素的顺序。那么假如说我们有两个栈stack1, stack2。那么一开始我们输入数据的时候，可以把它放到stack1里面，只要我们需要输出了，我们就看看stack2里面有没有元素。没有元素的话就把stack1里面的元素都pop出来，放到stack2里面。这样的话因为我们stack1是一个栈，数据的顺序与队列是反过来的，所以stack2里面的数据顺序就是队列的顺序，因此只要stack2不是空的，stack2的栈顶就是我们要的队列的第一个元素。

因为我们要的是第一个元素，所以pop, peek等方法怎么写，也就有数了。

好的，我们来看一下代码吧。

class MyQueue {
private:
    stack<int> inStack, outStack;
    void in2out() {
        while (!inStack.empty()) {
            outStack.push(inStack.top());
            inStack.pop();
        }
    }

public:
    MyQueue() {}
    void push(int x) {
        inStack.push(x);
    }

    int pop() {
        if (outStack.empty()) {
            in2out();
        }
        int x = outStack.top();
        outStack.pop();
        return x;
    }

    int peek() {
        if (outStack.empty()) {
            in2out();
        }
        return outStack.top();
    }

    bool empty() {
        return inStack.empty() && outStack.empty();
    }
};

这里的inStack和outStack就分别对应了我们之前的stack1和stack2。

Problem 3: Leetcode 155 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) —— 将元素 x 推入栈中。pop() —— 删除栈顶的元素。top() —— 获取栈顶元素。getMin() —— 检索栈中的最小元素。

区分于之前的设计题，这一个题多了一个求最小值的选项。在这里事实上注意到，我们也可以使用辅助栈来描述这个问题。

为什么可以？这是因为我们固定一组栈中元素的时候，这一组元素的最小值也就固定下来了。因此其实我们可以在辅助栈中对应存储这一组元素中的最小值。具体可以看下图。

说完这个细节，这个题就没啥特别的了，我们直接看代码。

MinStack() {
        min_stack.push(INT_MAX);
    }
    
    void push(int x) {
        x_stack.push(x);
        min_stack.push(min(min_stack.top(), x));
    }
    
    void pop() {
        x_stack.pop();
        min_stack.pop();
    }
    
    int top() {
        return x_stack.top();
    }
    
    int getMin() {
        return min_stack.top();
    }

这里的x_stack就是主栈，min_stack就是我们说的辅助栈。

Problem 4: Leetcode 71 给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。 在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。 请注意，返回的 规范路径 必须遵循下述格式： 始终以斜杠 '/' 开头。两个目录名之间必须只有一个斜杠 '/' 。最后一个目录名（如果存在）不能 以 '/' 结尾。此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。返回简化后得到的 规范路径 。

比方说如果有path = "/home/"，那么答案就是"/home"，因为最后一个目录名后面没有斜杠。如果有path = "/../"，那么答案就是"/"，因为从根目录向上一级是不可行的，根目录是你可以到达的最高级。

对于这个问题，很多人会想着通过模拟（简单来说就是从头到尾遍历一遍，一步步检查要求是否都做到了）来解决。这样子当然也可以，但是代码量也会比较大。事实上，学过Linux的朋友会知道，Linux内部处理这种目录分级就是利用了栈这个数据结构，所以我们这里也介绍一下栈的解决方法。

因为Linux内部是使用/进行分层级的，所以我们第一件事，就是按照/作拆分，把它拆成一个列表。这样的话，每一个列表内的元素，我们只需要观察这些情况，就可以得到我们的算法。

1. 准备一个栈。
2. 如果遇到了['.', '..', '']以外的内容，入栈。
3. 如果遇到了['..']并且栈非空，出栈。
4. 列表遍历结束之后，再用/将列表元素都拼接起来。

这里对应代码如下。

class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []
        for p in path.split('/'):
            if p not in ['.', '..', '']:
                stack.append(p)
            elif p == '..' and stack:
                stack.pop()
        return f"/{'/'.join(stack)}"

因为实在没有找到C++的版本，这里我们贴了一个Python的。

Problem 5: Leetcode 735 给定一个整数数组 asteroids，表示在同一行的行星。 对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。 找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。

比方说输入asteroids = [5,10,-5]，那么输出就是[5, 10]，因为从左到右的行星大小分别为[5, 10, 5]，只是最后一颗行星是向左运动的，所以最后两个就会相撞，最右边的那个5就爆炸了（注意，很明显题目没有让你考虑碰撞之后速度怎么变化，这是动量守恒才需要考虑的事情）。

对于这一个问题，我们可以思考一下。在我们枚举的时候，其实就相当于“不断在最右边的那个小行星中继续安插小行星“。在这个情况下，如果要发生爆炸，也必须要从右往左发生，因此实际上每一步遍历到新的元素之后，只需要考虑新的元素相邻的一个元素和它的运行情况即可。这就可以使用栈了。

具体来说，算法是这样的

1. 考虑栈顶元素top，一个新的小行星为new，那么如果new向右，或者top向左，都不会碰撞。
2. 否则，根据重量大小决定哪一个会爆炸，爆炸要记得pop，并且继续检查新元素与堆顶元素的情况（因为有可能继续爆炸）。

好的，我们来看看核心代码。

Stack<Integer> stack = new Stack();
for (int ast: asteroids) {
  collision: {
    while (!stack.isEmpty() && ast < 0 && 0 < stack.peek()) {
      if (stack.peek() < -ast) {
        stack.pop();
        continue;
      } else if (stack.peek() == -ast) {
        stack.pop();
      }
      break collision;
    }
    stack.push(ast);
  }
}

int[] ans = new int[stack.size()];
for (int t = ans.length - 1; t >= 0; --t) {
  ans[t] = stack.pop();
}
return ans;

还是一样，因为我们没有找到C++的代码，所以我们搬了一个Java的过来。

当然在这里，大家也要注意，这里的函数写法和之前的所有题目都有所不同，有点像匿名函数。是一个挺值得学习的巧妙的用法。读者如果不习惯这种写法，也可以换一种自己的写法，当然对我来说，我一般会学一学这种新的方法，毕竟师夷长技以制夷嘛。

一个类似的题目是Leetcode 1047，也是因为考虑到相邻元素而想到了栈这么一个数据结构，读者也可以拿它来练练手。

Problem 6: Leetcode 224 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。运算表达式中只有加减两个运算符，会有括号。

这一道题也是比较经典的，基本计算器类型的题目。对于这些题目我们只介绍它的变种1和2，另外其实计算表达式本身也是可以使用树和栈来完成的（逆波兰式），但这个碍于篇幅，我们就不多说了。

这一个题目只有加减运算，所以不用考虑太多先后计算的问题。充其量需要考虑的就是括号所在的位置。简单来说，我们需要一个栈，这个栈保存了当前括号对应的符号（我们之后解释含义）。然后在这个符号下，我们遇到一个数，就乘上当前栈顶保存的符号就可以了。

具体来说，我们设一开始栈顶默认为正号。假如说我们要分析1+2这种不带括号的，那么没什么好说的，遇到+就把当前的符号sign改成+，遇到-也同理。

如果有括号，那么要注意一个细节，就是括号前面是+，没问题。但如果是-，之后的符号都会改变。所以为了体现这一点，在遇到左括号的时候，我们会把当前的符号放到栈内，在遇到右括号的时候，就弹出一个栈顶的符号。这样的话，如果栈顶符号是-，说明括号前面是-，那么括号内如果再遇到+，就要把它当成-来看，相当于变号。这也是我们所说，栈用来保存“当前括号对应的符号”的含义。

这一段听起来还是怪复杂的。但是如果学过《算法与数据结构》，对于这一段分析不会太陌生。我们来看看代码吧。

int calculate(string s) {
        stack<int> ops;
        ops.push(1); // 一开始栈顶是+，就是+1
        int sign = 1;
        int ret = 0;
        int n = s.length();
        int i = 0;
        while (i < n) {
            if (s[i] == ' ') {
                i++;
            } else if (s[i] == '+') {
                sign = ops.top(); // 表示和括号表示的符号一致
                i++;
            } else if (s[i] == '-') {
                sign = -ops.top();// 表示和括号表示的符号相反。也就是说如果括号是+，那么遇到-当-看，如果括号是-，那么遇到-当+看。
                i++;
            } else if (s[i] == '(') {
                ops.push(sign);
                i++;
            } else if (s[i] == ')') {
                ops.pop();
                i++;
            } else {
                long num = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9') {
                    num = num * 10 + s[i] - '0';
                    i++;
                }
                ret += sign * num;
            }
        }
        return ret;
    }

结合着代码看，意思会明确很多。

Problem 7: Leetcode 227 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。有加减乘除，没有括号。 整数除法仅保留整数部分。

涉及到乘除法之后，因为涉及到运算顺序的改变，所以不可能遇到+/-之后直接就统计计算结果了。因此实际的情况是，在遇到乘除号运算的部分之后，先计算结果，然后等遇到了+, -之后，再把元素压入栈中。最后把栈中的元素加在一起就可以了。

具体的写法，我们直接放出代码，其实更直接明显一点。

int calculate(string s) {
  vector<int> stk;
  char preSign = '+';
  int num = 0;
  int n = s.length();
  for (int i = 0; i < n; ++i) {
    if (isdigit(s[i])) {
      num = num * 10 + int(s[i] - '0');
    }
    if (!isdigit(s[i]) && s[i] != ' ' || i == n - 1) {
      switch (preSign) {
        case '+':
          stk.push_back(num);
          break;
        case '-':
          stk.push_back(-num);
          break;
        case '*':
          stk.back() *= num;
          break;
        default:
          stk.back() /= num;
      }
      preSign = s[i];
      num = 0;
    }
  }
  return accumulate(stk.begin(), stk.end(), 0);
}

流程应该不是很难懂，就不多解释了。

单调栈

在接下来的篇幅中，我们主要开始介绍单调栈这么一个算法。单调栈的理解还是有一点难度的，在Leetcode中也有很多类似的习题，因此值得单独拉出来说一说。

Problem 8: Leetcode 402 给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。如果最终的数字有前导0，需要删除（不计入移除的

个内）

比方说输入num = "1432219", k = 3，那么答案就是1219，相当于去掉了三个数字4, 3, 2。

首先分析这个问题。对于一个数字而言，靠前位置的数的大小，会决定整个数的大小（比方说3x > 2y（三十多一定大于二十多），无论

是多少）。因此基本的策略就是从前往后一直枚举，一直找到相邻的两位数

满足

（

是靠前的位数），那么相比较删去

，删去

就可以得到一个更小的数字。而且因为越靠前的位置越重要，所以找到的第一个符合条件的元素，就可以删去。如果一直找不到，说明序列是非下降的，那么删除最后一个元素。这个过程一直做

次就可以了。

现在我们会遇到一个问题，就是有可能会出现，每一次都要枚举所有位的情况。因此这个时候，复杂度就差不多是

，相对较大。解决这个问题更好的方法就是单调栈。简单来说，维护一个单调序列而使用的栈。

具体的做法，大概可以概括为如下：

对于每个数字，如果该数字小于栈顶的元素，就不断弹出栈顶元素，直到栈为空，或者新的栈顶元素不大于当前数字，或者已经删除了

位数字。

这里可以用单调栈来解决，原因也是在于，当栈顶元素不小于需要进入栈的元素的时候，说明这个时候，前一位数字大于后一位数字了，就需要把前一位数字删掉，直至符合要求。

这里还有一些细节。前导0的处理是一种，最终可能删不到

个元素，那么如果只删除了

个，就需要删除最后的

个。最终如果序列为空，那需要输出0。

好的，我们来看一下核心代码吧。

string removeKdigits(string num, int k) {
        vector<char> stk;
        for (auto& digit: num) {
            while (stk.size() > 0 && stk.back() > digit && k) {
                stk.pop_back();
                k -= 1;
            }
            stk.push_back(digit);
        }

        for (; k > 0; --k) {
            stk.pop_back();
        }

        string ans = "";
        bool isLeadingZero = true;
        for (auto& digit: stk) {
            if (isLeadingZero && digit == '0') {
                continue;
            }
            isLeadingZero = false;
            ans += digit;
        }
        return ans == "" ? "0" : ans;
    }

这里是使用了C++的vector库来模拟的栈。

Problem 9: Leetcode 321 给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。 求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。

这个题也是一个数位有关的题目。可以看出，对于这个题要做两步，第一步是在每一个数组中，找到一个合适的序列。第二步，就是把两个序列合并。

什么是合适的序列？要找到一个最大的合并序列，那么很明显，每一个数组中它也最好是一个最大序列。而这个最大序列的获得方法，其实就是上一个问题，单调栈方法的一个变形。Problem 6中，我们通过单调栈找到了一串数中最小的。那么这个题，我们就把判断方法换一下，就可以找到一串数中最大的。具体怎么做交给读者思考。

第一步说明白了，再看看合并序列应该怎么做。事实上，和合并排序的思路一致。设置两个指针之后，观察所指位置的哪一个元素是更大的，更大的就合并到新的数组中。如果所指的元素值相同，那么就继续往后面看。比方说两个指针都指向了5，结果数组A中，5的下一个是8，数组B中，5的下一个是7，那就应该把A中的5合并进新的数组。

最后还有一个细节，就是我们一共要找

位数字，这可能有很多种情况。你可以第一个数组找1位，第二个数组找

位，也可以第一个数组找2位，第二个数组找

位，以此类推。所以这里也需要注意枚举可能的选择的位数，并注意不要超过数组本身的长度。

说完这些，我们来看看核心代码吧。

class Solution:
    def maxNumber(self, nums1, nums2, k):

        def pick_max(nums, k):
            stack = []
            drop = len(nums) - k
            for num in nums:
                while drop and stack and stack[-1] < num:
                    stack.pop()
                    drop -= 1
                stack.append(num)
            return stack[:k]

        def merge(A, B):
            ans = []
            while A or B:
                bigger = A if A > B else B
                ans.append(bigger.pop(0))
            return ans

        return max(merge(pick_max(nums1, i), pick_max(nums2, k-i)) for i in range(k+1) if i <= len(nums1) and k-i <= len(nums2))

这里我们用了Python的题解，因为官网的C++题解感觉不如这个写得好hhh。

Problem 10: Leetcode 135 老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。 你需要按照以下要求，帮助老师给这些孩子分发糖果： 每个孩子至少分配到 1 个糖果。评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。那么这样下来，老师至少需要准备多少颗糖果呢？

对于这个问题，其实大家可以发现，无非就是要寻找一些所谓的“谷底”，因为这种元素，它的左边和右边的元素都比它要大，所以对于这些分的人，所需要做的事情就是给他1个糖果，然后依次向左向右拓展即可（比方说谷底左边的一个元素比它大，那么就必须要给2个糖果，再左边的元素如果比这个元素大，那就需要给3个糖果，以此类推）。

对于这个问题，官方没有给出单调栈的解法（当然本身它的方法也很重要，我们会在之后重提这一道题），我们这里给出一个这样的解法。注意到我们其实关键就是要找到“谷底”。所以什么是谷底呢？就是一个下降序列的最后一个元素。

这里就可以使用单调栈了，因为我们可以用单调栈维护一个下降的序列，然后只要有一个元素它比栈顶元素要大，就说明谷底元素已经出现了，那么直接记录，然后让栈的元素都清空就可以了。

好的，我们来看一下核心代码。

int candy(vector<int>& ratings) {
  ratings.push_back(INT_MAX);
  int n = ratings.size();
  vector<int> res(n, 1);
  stack<int> st;
  int sum = 0;
  for (int i = 0; i < n; ++i) {
    if (!st.empty() && ratings[i] >= ratings[st.top()]) {
      while (!st.empty()) {
        int j = st.top();
        st.pop();
        if (j < n-1 && ratings[j] > ratings[j+1]) {
          res[j] = max(res[j], res[j+1]+1);
        }
        if (j > 0 && ratings[j] > ratings[j-1]) {
          res[j] = max(res[j], res[j-1]+1);
        }
        sum += res[j];
      }
    }
    st.push(i);
  }
  return sum;
}

Problem 11: Leetcode 907 给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。 由于答案可能很大，因此 返回答案模 10^9 + 7 。

举个例子，如果arr = [3,1,2,4]，那么输出17，因为它的子数组有[3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]，对应的每一个子数组的最小值加在一起就是17。

这个题如何解呢？其实如果要枚举它所有的子数组，必然是很浪费时间的。但是我们可以反过来想，对于每一个元素，只需要找到最大的可以包括它的子数组就可以了。因为假如说

内的最小值是

，并且

不在边缘，那么

内的最小值也必然是

。换句话说，我们的做法是固定某一个值，然后去观察这个值属于多少个区间。

那么这个“最大的”区间怎么找呢？不妨看看左边，如果要求某一个元素

是区间内的最小值，那么这个

左边的元素一定都要比它大。所以这样的话，用单调栈维护一个单调上升的子序列，你会发现，当

大于栈顶的时候，不断地出栈，一直到遇到一个比

小的元素的时候，这个比

小的元素，和

中间的所有元素都是不小于

的，也就是最大的，向左可以伸展的距离。

向右计算也是同理的，所以我们可以得到每一个元素所对应的最左边和最右边的最大区间范围，那么计算的时候，把左边可以伸展的距离和右边可以伸展的距离相乘，就是可选的子数组个数了。

但是这样算有个问题，就是我们如果最小值遇到了相同的元素，应该如何处理？举个例子，假如一个区间是[1, 2, 3, 4, 1]，那么这个区间的最小值有2个，但是上面的方法就会把这个区间的最小值计算两次。所以计算的时候有个技巧，就是对于一个元素而言，如果左边计算的时候我们的要求是“区间内所有的元素都不小于

“，那么右边计算的时候就严格要求，要求右边的区间内，所有的元素都要大于

，相当于等号只允许成立一边，要不左边，要不右边。这样的话，上面说的这种重复情况，就可以被排除了。

好的，我们来看一下代码

int sumSubarrayMins(vector<int>& A) {
  int n = A.size();
  vector<int> pre(n, 0), nxt(n, 0);
  stack<int> sp, sn;
  for (int i = 0; i < n; ++i) {
    while (!sp.empty() && A[sp.top()] >= A[i]) sp.pop();
    pre[i] = sp.empty() ? i + 1 : i - sp.top();
    sp.push(i);
  }
  for (int i = n-1; i >= 0; --i) {
    while (!sn.empty() && A[sn.top()] > A[i]) sn.pop();
    nxt[i] = sn.empty() ? n - i : sn.top() - i;
    sn.push(i);
  }
  int res = 0;
  for (int i = 0; i < n; ++i) {
    (res += ((pre[i] * nxt[i]) % MOD * A[i]) % MOD) %= MOD;
  }
  return res;
}

这个题虽然是一个medium难度，但是还是需要多考虑的。

小结

这一节我们主要介绍了利用栈和队列这两个结构来求解的一些问题。也介绍了几道单调栈方法应用的习题。这一些题目各自都具有一些技巧，需要仔细思考和设计才能比较好的完成。

下一节我们来介绍一些树相关的内容。树结构可以考察的点也很多，相信也会是充实的一节hhh