切换主题
单调栈篇
什么时候考虑用单调栈？
求解问题答案的过程中只要涉及到：需要求解元素的前后的最近的较大/小值，就可以考虑使用单调栈（栈内存储的是元素的下标）！
为什么栈内存储的是元素下标而不是元素值？
根据数组的特性，我们可以通过数组的下标轻易（时间复杂度来考量）的获得对应元素及其位置信息，当然某些情况下你也可以存储键值对！
为什么这类问题要考虑使用单调栈？
因为可以通过使用单调栈将原本
O(n^2)的时间复杂度优化到O(n)。如何优化？当我们在遍历数据的过程中，同时维护着一个单调栈（以单调递减栈为例）， 这个单调栈有这样的一个特性：当我们遍历到一个大于栈顶元素对应值的元素（记为A[i]）时，
- 将栈顶元素出栈，得到下标
idx = stack.pop()（位置信息），此时的A[i]就是栈顶元素对应值（记为A[idx]）右侧的最近较大元素；- 而此时
新栈顶元素的对应值便是A[idx]左侧的最近较大元素。
如何维护单调栈？
单调栈主要分为单调递减栈和单调递增栈。以单调递减栈为例，在遍历数组的过程中：
- 当
当前元素值小于等于栈顶元素对应值时，直接将当前元素对应的下标压入栈中，继续遍历；- 当遇见大于
栈顶元素对应值的元素时，开始弹栈（弹栈后涉及答案计算），直到栈为空或者栈顶元素对应值小于等于当前元素值才停止弹栈，并将当前元素的下标压入栈中。
举个例子：假设我们现在需求出A = [3, 2, 5, 1, 6]中每个元素最近的下一个更大值的距离
- 当遍历到元素
5时（i === 2），此时的单调栈为stack = [0, 1]，由于当前元素A[i]大于栈顶元素对应值A[stack[stack.length - 1]]， 即5 > 2，弹栈(idx=stack.pop()) === 1，故元素2的最近的下一个更大值的距离为(i - idx) = 2 - 1，此时的栈为stack = [0]； - 由于新的栈顶元素（
idx === 0）对应值A[0] === 3依然小于当前元素A[i] === 5，继续弹栈，故元素3的最近的下一个更大值的距离为(i - idx) = 2 - 0； - 后面的元素以此类推。
单调递减栈解题模板：
JavaScript
const template = A => {
// 声明单调栈，存放下标
const stack = []
// 遍历数组
for (let i = 0; i < A.length; i++) {
// 判断当前元素与栈顶元素大小关系
while (stack.length && A[i] > A[stack[stack.length - 1]]) {
// 弹栈
const idx = stack.pop()
if (stack.length) break
const idxL = stack[stack.length - 1]
// do something
}
// 压栈
stack.push(i)
}
return 结果
}单调递增栈与单调递减栈原理类似，这里就不过多赘述了。
每日温度
解题思路
JavaScript
const dailyTemperatures = T => {
const len = T.length
const [ret, stack] = [Array(len).fill(0), []]
for (let i = 0; i < len; i++) {
while (stack.length && T[i] > T[stack[stack.length - 1]]) {
const idx = stack.pop()
ret[idx] = i - idx
}
stack.push(i)
}
return ret
}时间复杂度：O(n)；空间复杂度：O(n)。
接雨水
JavaScript
const trap = H => {
const stack = []
let ret = 0
for (let i = 0; i < H.length; i++) {
while (stack.length && H[i] > H[stack[stack.length - 1]]) {
const idx = stack.pop()
if (!stack.length) break
const idxL = stack[stack.length - 1]
const width = i - idxL - 1
const height = Math.min(H[idxL], H[i]) - H[idx]
ret += width * height
}
stack.push(i)
}
return ret
}时间复杂度：O(n)；空间复杂度：O(n)。
最大矩形
JavaScript
const largestRectangleArea = H => {
H = [0, ...H, 0]
const stack = []
let max = 0
for (let i = 0; i < H.length; i++) {
while (stack.length && H[i] < H[stack[stack.length - 1]]) {
const idx = stack.pop()
if (!stack.length) break
const idxL = stack[stack.length - 1]
const width = i - idxL - 1
max = Math.max(max, width * H[idx])
}
stack.push(i)
}
return max
}时间复杂度：O(n)；空间复杂度：O(n)。
最大矩形 II
JavaScript
const maximalRectangle = matrix => {
if (matrix.length === 0 || matrix[0].length === 0) return 0
const H = Array(matrix[0].length).fill(0)
let ret = 0
for (const str of matrix) {
for (let i = 0; i < str.length; i++) {
H[i] = str.charAt(i) === '0' ? 0 : H[i] + 1
}
ret = Math.max(ret, largestRectangleArea(H))
}
return ret
}时间复杂度：O(n)；空间复杂度：O(n)。