顾名思义，单调栈即元素单调递增或递减排列的栈。我们可以通过单调栈求元素的左（右）边第一个比他大（小）的元素。
例如我们想求数组里每个元素的左边第一个比它小的元素，我们可以维护一个严格单调增的栈，我们从前往后遍历原数组，设当前元素为num:
- 我们不断去掉栈顶元素直到栈空或者栈顶元素小于num，此时栈顶元素就是num的左边第一个比它小的元素，记录结果，然后将num入栈。
整个过程的复杂度为 O(n) ，因为所有元素只会进栈出栈一次。
vector<int> PreviousSmallerElement(vector<int>& nums) {
/*
求数组里每个元素的左边第一个比它小的元素，若找不到用-1填充
*/
vector<int> res(nums.size());
stack<int> monoStack;
for (int i = 0; i < nums.size(); i++) {
while (!monoStack.empty() && monoStack.top() >= nums[i])
monoStack.pop();
res[i] = monoStack.empty() ? -1 : monoStack.top();
monoStack.push(nums[i]);
}
return res;
}LeetCode上面可以用单调栈解决的题还挺多的：
- 42. Trapping Rain Water
- 84. Largest Rectangle in Histogram
- 85. Maximal Rectangle
- 456. 132 Pattern
- 496. Next Greater Element I
- 503. Next Greater Element II
- 739. Daily Temperatures
- 901. Online Stock Span
与单调栈类似，单调队列即元素单调递增或递减排列的队列。我们可以通过单调队列求滑动窗口的最值问题。一般用双向队列deque实现。
例如我们想求大小为k的滑动窗口内部的最大值（LeetCode239），那么核心思路就是用一个deque存放有可能成为最大值的元素（的下标）。从左往右滑动窗口的过程中，若窗口即将把nums[i]包含进来，
- 首先，若队首元素下标小于
i - k，即队首在窗口之外了，所以应该删除队首元素； - 然后，由于我们仅保留有可能成为最大值的元素（的下标），所以我们应该从队尾开始不断去掉比
nums[i]小的那些元素（的下标），因为只要窗口内有nums[i]，那么去掉的这些元素就不可能成为最大值。 - 最后，我们将
nums[i]（的下标）送入队尾。
因此，按照上述过程维护的队列里面的元素是单调递减的，队首的元素即每次窗口内的最大值。
每个元素入队出队一次，时间复杂度O(n)，且仅遍历一次数组。
滑动窗口最值问题还有一个同样O(n)的思路，具体见239题解思路二。
// Leetcode 239
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int>res;
deque<int>win;
for(int i = 0; i < nums.size(); i++){
if (!win.empty() && win.front() == i - k) win.pop_front();
while(!win.empty() && nums[win.back()] <= nums[i]) win.pop_back();
win.push_back(i);
if(i >= k - 1) res.push_back(nums[win.front()]);
}
return res;
}