昨日回顾
昨天我们开启了栈这个数据结构的章节，分别介绍了Python和Java中栈的初始化与使用。然后通过三道题目，对栈的解题和分析有了一个初步的了解。
然而昨天的栈题目，主要是针对题目的条件，判断是否需要弹出栈内元素，属于通用的栈场景。然而，今天需要介绍的是栈中特殊的一类题目，单调栈。
既然是单调的，那么要么单调增、要么单调减。当我们遇到一道题目时，如何判断是否该使用单调栈的方法去解题呢？这里要注意，单调栈的题目，最通用的关键字是下一个、更大(小)的 等等。
而主要的单调栈思路就是，需要不断根据数组后续的内容，来获得更大、更优的解。
说了这么多，主要是让大家有一个初步的概念，然后在通过后续的题目的分析，深入的理解这类题目的特点。先来看一道比较明显的单调栈问题吧。
剑指OfferII038.每日温度
https://leetcode-cn.com/problems/iIQa4I/solution/shua-chuan-jian-zhi-offer-day18-zhan-ii-mdv06/
难度：中等
题目：
请根据每日 气温 列表 temperatures ，重新生成一个列表，要求其对应位置的输出为： 要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
提示：
- 1 <= temperatures.length <= 10 ^ 5
- 30 <= temperatures[i] <= 100
示例：
示例 1: 输入: temperatures = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0] 示例 2: 输入: temperatures = [30,40,50,60] 输出: [1,1,1,0] 示例 3: 输入: temperatures = [30,60,90] 输出: [1,1,0]
分析
这是一道比较典型的单调栈问题。 根据题意我们需要找到下一个更高的气温，然后计算两者相差的天数。 这里注意，如果气温在这之后都不会升高，则将该位置用0来代替。
- 根据以上的信息，我们可以先创建一个temperatures等长的全零数组，然后初始化一个栈
- 这里注意由于需要返回相差天数，所以栈中需要保存元素下标来实现天数计算。
- 下来循环temperatures进行栈的操作，循环过程中，持续判断当前下标温度与栈顶下标温度的大小差别
- 如果当前下标的温度大于栈顶下标的温度，表示找到了下一个更大的温度，弹出栈顶下标，计算天数差别， 更新ret[栈顶下标] = 当前下标 - 栈顶下标
- 否则将当前下标加入栈顶
- ret中没有更新的元素，表示未找到更高的温度，最终返回ret即可。
这里模拟题目中示例1，给出栈和ret的变化，供大家参考：
- 输入: temperatures = [73,74,75,71,69,72,76,73]
- 输出: [1,1,4,2,1,1,0,0]
| 下标 -> 元素 | 栈 | 等待天数 | 说明 |
| 0 -> 73 | [73] | [0, 0, 0, 0, 0, 0, 0, 0] | 0入栈 |
| 1 -> 74 | [74] | [1, 0, 0, 0, 0, 0, 0, 0] | 0出栈、1入栈 |
| 2 -> 75 | [75] | [1, 1, 0, 0, 0, 0, 0, 0] | 1出栈、2入栈 |
| 3 -> 71 | [75, 71] | [1, 1, 0, 0, 0, 0, 0, 0] | 3入栈 |
| 4 -> 69 | [75, 71, 69] | [1, 1, 0, 0, 0, 0, 0, 0] | 4入栈 |
| 5 -> 72 | [75, 72] | [1, 1, 0, 2, 1, 0, 0, 0] | 3、4出栈，5入栈 |
| 6 -> 76 | [76] | [1, 1, 4, 2, 1, 1, 0, 0] | 2、5出栈、6入栈 |
| 7 -> 73 | [76, 73] | [1, 1, 4, 2, 1, 1, 0, 0] | 7入栈 |
解题：
Python:
class Solution: def dailyTemperatures(self, temperatures): stack, ret = [], [0] * len(temperatures) for i, num in enumerate(temperatures): while stack and temperatures[stack[-1]] < num: index = stack.pop() ret[index] = i - index stack.append(i) return ret
Java:
class Solution { public int[] dailyTemperatures(int[] temperatures) { Stack<Integer> stack = new Stack<>(); int[] ret = new int[temperatures.length]; for (int i = 0; i < temperatures.length; i++) { while (!stack.empty() && temperatures[stack.peek()] < temperatures[i]) { int index = stack.pop(); ret[index] = i - index; } stack.push(i); } return ret; } }
有了这道题目作为单调栈思维的入门，相信大家在基本套路上已经有所了解了。下来，我们在做一个同类型、同难度的单调栈问题，检验下大家是否掌握了这种方法。
503.下一个更大元素II
难度：中等
题目：
给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。
数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的
下一个更大的数。如果不存在，则输出 -1。
注意: 输入数组的长度不会超过 10000。
示例：
输入: [1,2,1] 输出: [2,-1,2] 解释: 第一个 1 的下一个更大的数是 2； 数字 2 找不到下一个更大的数； 第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
分析
做过上一题，根据单调栈计算下标差值的实现，相信想通过这道题也不会有太大难度。由于题目差异不大，在这里就简单分析下吧。
首先我们维护一个ret = [-1] * len(nums)的数组，由于是循环数组，所以我们需要循环两次nums，使用单调栈的方式存储下标。
如果找到比栈顶大的元素，则对栈内存储的下标对应的ret赋值。
解题：
Python:
class Solution: def nextGreaterElements(self, nums): ln = len(nums) ret = [-1] * ln stack = [] for i in range(ln * 2 - 1): while stack and nums[stack[-1]] < nums[i % ln]: ret[stack.pop()] = nums[i % ln] stack.append(i % ln) return ret
Java:
class Solution { public int[] nextGreaterElements(int[] nums) { int lg = nums.length; int[] ret = new int[lg]; Arrays.fill(ret, -1); Stack<Integer> stack = new Stack<>(); for (int i = 0; i < lg * 2 - 1; i++) { while (!stack.empty() && nums[stack.peek()] < nums[i % lg]){ ret[stack.pop()] = nums[i % lg]; } stack.push(i % lg); } return ret; } }
剑指OfferII039.直方图最大矩形面积
https://leetcode-cn.com/problems/0ynMMM/
难度：困难
题目：
给定非负整数数组 heights ，数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
提示：
- 1 <= heights.length <=105
- 0 <= heights[i] <= 104
示例：
image.png
分析
首先我们需要明确的是，什么时候入栈什么时候出栈？
通过图例我们也可以发现，如果当前元素比栈顶元素大时，我们入栈并继续计算下一个。如果当元素小于栈顶元素时，将位于栈顶的柱子的下标出栈，并且计算以位于栈顶的柱子为顶的最大矩形面积。
那么，如果数组时单调递增的，岂不是一直入栈没有返回了？记得之前我们在数组章节介绍过哨兵节点，所以在单调栈这种求最大值的时候，也需要设置哨兵节点。即设置左右两端点的高度为0，则可以在初始计算及最终结果时，能够完整计算所有面积。
如果还不明确，可以按照温度那道题，创建一个表格填写一下每一步的操作过程，会更利于大家去学习。
最终代码如下：
解题：
Python:
class Solution: def largestRectangleArea(self, heights): stack, ret = [], 0 heights= [0] + heights + [0] for i in range(len(heights)): while stack and heights[i] < heights[stack[-1]]: h = heights[stack.pop()] ret = max(ret, h * (i - 1 - stack[-1])) stack.append(i) return ret
Java:
class Solution { public int largestRectangleArea(int[] heights) { int res = 0; Stack<Integer> stack = new Stack<>(); int[] new_heights = new int[heights.length + 2]; for (int i = 1; i < heights.length + 1; i++) { new_heights[i] = heights[i - 1]; } for (int i = 0; i < new_heights.length; i++) { while (!stack.empty() && new_heights[i] < new_heights[stack.peek()]) { int h = new_heights[stack.pop()]; res = Math.max(res, (i - stack.peek() - 1) * h); } stack.push(i); } return res; } }
