写在前
单调栈（monotone-stack）是指栈内元素（栈底到栈顶）都是（严格）单调递增或者单调递减的。
如果有新的元素入栈，栈调整过程中 会将所有破坏单调性的栈顶元素出栈，并且出栈的元素不会再次入栈 。由于每个元素只有一次入栈和出栈的操作，所以 单调栈的维护时间复杂度是O(n) 。
单调栈性质：
- 单调栈里的元素具有单调性。
- 递增（减）栈中可以找到元素左右两侧比自身小（大）的第一个元素。
我们主要使用第二条性质，该性质主要体现在栈调整过程中，下面以自栈底到栈顶递增为例（假设所有元素都是唯一），当新元素入栈。
- 对于出栈元素来说：找到右侧第一个比自身小的元素。
- 对于新元素来说：等待所有破坏递增顺序的元素出栈后，找到左侧第一个比自身小的元素。
1.单调栈结构
问题描述：给定不含重复值的数组arr，找到每个i位置左边和右边距离i最近的且值比i小的位置(没有返回-1)，返回所有的位置信息。
进阶问题：数组中含有重复值。
示例：
arr = {3, 4, 1, 0} { {-1, 2}, {0, 2}, {-1, 3}, {-1, -1} }
思路：常规时间复杂度O(n^2)实现简单，每个位置向左和向右遍历一遍。
单调栈实现：寻找两边距离arr[i]最近且arr[i]小的索引，保持栈顶到栈底单调递减（寻找比arr[i]大的值，单调递增），栈中存放索引值。
对于进阶问题，区别在于重复索引值用集合进行连接，栈中存放的是一个ArrayList。注意两点：
- arr[i]左边应该是上一个位置最晚加入的那个（如果有多个元素）
- 相等的情况直接在尾部加入，获取值的时候循环的获取该集合中的所有值（集合中元素值相等，索引值不同）
代码：原问题
public int[][] getNearLessNoRepeat(int[] arr) { int[][] ans = new int[arr.length][2]; Stack<Integer> stack = new Stack<>(); // 遍历数组，入栈 for (int i = 0; i < arr.length; ++i) { while (!stack.isEmpty() && arr[i] < arr[stack.peek()]) { int popIndex = stack.pop(); int leftLessIndex = stack.isEmpty() ? -1 : stack.peek(); ans[popIndex][0] = leftLessIndex; ans[popIndex][1] = i; } stack.push(i); } while (!stack.isEmpty()) { int popIndex = stack.pop(); int leftLessIndex = stack.isEmpty() ? -1 : stack.peek(); ans[popIndex][0] = leftLessIndex; // 说明该索引右边没有比当前小的元素，有的话该索引在上边循环就弹出了 ans[popIndex][1] = -1; } return ans; }
代码：进阶问题
public int[][] getNearLess(int[] arr) { int[][] ans = new int[arr.length][2]; Stack<List<Integer>> stack = new Stack<>(); // 遍历数组，入栈 for (int i = 0; i < arr.length; ++i) { while (!stack.isEmpty() && arr[i] < arr[stack.peek().get(0)]) { List<Integer> popIs = stack.pop(); int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1); for (int popi : popIs) { ans[popi][0] = leftLessIndex; ans[popi][1] = i; } } if (!stack.isEmpty() && arr[i] == arr[stack.peek().get(0)]) { stack.peek().add(Integer.valueOf(i)); } else { ArrayList<Integer> list = new ArrayList<>(); list.add(i); stack.push(list); } } while (!stack.isEmpty()) { List<Integer> popIs = stack.pop(); int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1); for (int popi : popIs) { ans[popi][0] = leftLessIndex; ans[popi][1] = -1; } } return ans; }
2.下一个更大的元素（leetcode496-易）
题目描述：给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
示例：
输入: nums1 = [4,1,2], nums2 = [1,3,4,2]. 输出: [-1,3,-1] 解释: 对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。 对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。 对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
思路：维护一个从栈顶到栈底的严格单调递增的栈，先遍历大数组记录每个元素右边第一个比当前元素大的值，然后遍历小数组输出结果。这里用一个hashmap映射两个数组的元素，栈中元素这里仍是索引，也可用元素。
代码：
public int[] nextGreaterElement(int[] nums1, int[] nums2) { Stack<Integer> stack = new Stack<>(); HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums2.length; ++i) { while (!stack.isEmpty() && nums2[i] > nums2[stack.peek()]) { int cur = stack.pop(); int rightMaxIdx = i; map.put(nums2[cur], nums2[rightMaxIdx]); } stack.push(i); } int[] ans = new int[nums1.length]; for (int j = 0; j < nums1.length; ++j) { ans[j] = map.getOrDefault(nums1[j], -1); } return ans; }
3.柱状图中最大的矩形（leetcode84-难）
问题描述：给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例：
输入: [2,1,5,6,2,3] 输出: 10
思路：有了单调栈的基本认识，我们可以遍历每根柱子，以当前柱子 i 的高度作为矩形的高，那么矩形的宽度边界即为向左找到第一个高度小于当前柱体 i 的柱体，向右找到第一个高度小于当前柱体 i 的柱体。对于每个柱子我们都如上计算一遍以当前柱子作为高的矩形面积，最终比较出最大的矩形面积即可。
单调栈实现：寻找两边距离arr[i]最近且arr[i]小的索引，保持栈顶到栈底单调递减，栈中存放索引值。
注意：头0如果不添加，寻找左边元素需要判断栈是否为空；尾0如果不添加，需要重新写一个循环弹出栈内元素。
代码：原问题
class Solution { // 单调栈（栈底到栈顶单调递增） public int largestRectangleArea(int[] heights) { int n = heights.length; Deque<Integer> stack = new LinkedList<>(); int ans = 0; for (int i = 0; i < n; i++) { while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) { int curIndex = stack.pop(); while (!stack.isEmpty() && heights[stack.peek()] == heights[curIndex]) { stack.pop(); } int leftIndex = stack.isEmpty() ? -1 : stack.peek(); ans = Math.max(ans, (i - leftIndex - 1) * heights[curIndex]); } stack.push(i); } while (!stack.isEmpty()) { int curIndex = stack.pop(); while (!stack.isEmpty() && heights[stack.peek()] == heights[curIndex]) { stack.pop(); } int width = stack.isEmpty() ? n : n - stack.peek() - 1; ans = Math.max(ans, width * heights[curIndex]); } return ans; } // 优化1：添加尾0(推荐) public int largestRectangleArea(int[] heights) { int n = heights.length; heights = Arrays.copyOf(heights, n + 1); Deque<Integer> stack = new LinkedList<>(); int ans = 0; for (int i = 0; i < n + 1; i++) { while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) { int curIndex = stack.pop(); while (!stack.isEmpty() && heights[stack.peek()] == heights[curIndex]) { stack.pop(); } int leftIndex = stack.isEmpty() ? -1 : stack.peek(); ans = Math.max(ans, (i - leftIndex - 1) * heights[curIndex]); } stack.push(i); } return ans; } // 优化2：首尾都扩容0 public int largestRectangleArea(int[] heights) { int n = heights.length; int[] tmp = new int[n + 2]; System.arraycopy(heights, 0, tmp, 1, n); Deque<Integer> stack = new LinkedList<>(); int ans = 0; for (int i = 0; i < n + 2; i++) { while (!stack.isEmpty() && tmp[i] < tmp[stack.peek()]) { int curIndex = stack.pop(); while (!stack.isEmpty() && tmp[stack.peek()] == tmp[curIndex]) { stack.pop(); } int leftIndex = stack.peek(); ans = Math.max(ans, (i - leftIndex - 1) * tmp[curIndex]); } stack.push(i); } return ans; } }
4. 最大矩形（leetcode85-难）
题目描述：给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例：
image.png
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 输出：6 解释：最大矩形如上图所示。
思路：本题与上题思路相同，这里我们每遍历一行，更新代表柱子高度的函数heights。当前单元为0，高度为0；当前单元为1，高度+1.
利用动态规划的思想，我们不需要重新遍历之前走过的行，每遍历一行更新一下矩阵的最大面积。计算当前区域的最大矩形面积可以直接调用T84。
代码：
public int maximalRectangle(char[][] matrix) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0; int row = matrix.length, col = matrix[0].length; int[] heights = new int[col]; int ans = 0; for (int i = 0; i < row; ++i) { for (int j = 0; j < col; ++j) { if (matrix[i][j] == '0') heights[j] = 0; else ++heights[j]; } ans = Math.max(ans, largestRectangleArea(heights)); } return ans; } public int largestRectangleArea(int[] heights) { int[] tmp = new int[heights.length + 2]; System.arraycopy(heights, 0, tmp, 1, heights.length); int maxArea = 0; Deque<Integer> stack = new LinkedList<>(); for (int i = 0; i < tmp.length; ++i) { while (!stack.isEmpty() && tmp[i] < tmp[stack.peek()]) { int h = tmp[stack.pop()]; maxArea = Math.max(maxArea, (i - stack.peek() - 1) * h); } stack.push(i); } return maxArea; }
5.接雨水（leetcode42-难）
题目描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
思路：由示例我们可以看出上述可以划分为四部分积水区域，积水槽一定在两个柱子之间。只有左右元素都大于当前元素才能形成槽，那么可以维护从栈底到栈顶单调递减的单调栈：
- 这样可以找到左边第一个大于当前元素的值，当右边即将加入的值也大于它就形成了槽
- 栈中存放柱子对应的索引值。
- 注意：高的取值，边界较小的与当前槽高度的差值
代码：
class Solution { // 单调栈（从栈底到栈顶单调递减） public int trap(int[] height) { if (height == null || height.length == 0) { return 0; } Deque<Integer> stack = new LinkedList<>(); int ans = 0; for (int i = 0; i < height.length; i++) { while (!stack.isEmpty() && height[i] > height[stack.peek()]) { int curIndex = stack.pop(); // 优化：如果栈顶元素相等，则一直弹出，只留一个 while (!stack.isEmpty() && height[stack.peek()] == height[curIndex]) { stack.pop(); } if (!stack.isEmpty()) { int leftIndex = stack.peek(); ans += (i - leftIndex - 1) * (Math.min(height[leftIndex], height[i]) - height[curIndex]); } } stack.push(i); } return ans; } }
6.求区间最小数乘区间和的最大值（补充：字节高频面试题）
题目描述：给定一个数组，要求选出一个区间, 使得该区间是所有区间中经过如下计算的值最大的一个：区间中的最小数 * 区间所有数的和。注：数组中的元素都是非负数。
示例：
输入两行，第一行n表示数组长度，第二行为数组序列。输出最大值。
输入 3 6 2 1 输出 36 解释：满足条件区间是[6] = 6 * 6 = 36;
思路：最优解单调栈，注意单调栈内存的是索引
法1：使用暴力解，我们可以枚举数组中的最小值，然后向两边进行扩展，找到第一个比x小的元素，在寻找区间的过程中计算区间和。
法2：空间换时间，我们找边界的过程中可以使用单调栈，每个元素只进栈出栈一次，算法复杂度降到O(N)。这里在计算区间和时可以使用前缀和。
代码：
import java.util.Deque; import java.util.LinkedList; import java.util.Scanner; public class Solution004 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] nums = new int[n]; int i = 0; while (n-- > 0) { nums[i++] = sc.nextInt(); } // System.out.println(solution(nums)); System.out.println(solution1(nums)); } public static int solution(int[] nums) { int n = nums.length; int l = 0, r = 0; int sum = 0; int max = 0; for (int i = 0; i < n; i++) { sum = nums[i]; l = i - 1; r = i + 1; while (l >= 0 && nums[l] >= nums[i]) { sum += nums[l--]; } while (r < n && nums[r] >= nums[i]) { sum += nums[r++]; } max = Math.max(max, sum * nums[i]); } return max; } // 单调栈优化 public static int solution1(int[] nums) { int n = nums.length; int l = 0, r = 0; int max = 0, cur = 0; Deque<Integer> stack = new LinkedList<>(); //前缀和便于快速求区间和，例如求[l,r]区间和=dp[r+1]-dp[l]。l和r的取值范围是[0,n) int[] sums = new int[n + 1]; for (int i = 1; i <= n; i++) { sums[i] = sums[i - 1] + nums[i - 1]; } for (int i = 0; i < n; i++) { while (!stack.isEmpty() && nums[i] <= nums[stack.peek()]) { cur = nums[stack.pop()]; //l和r是边界，因此区间是[l+1,r-1]，其区间和dp[r]-dp[l+1] l = stack.isEmpty() ? -1 : stack.peek(); r = i; max = Math.max(max, cur * (sums[r] - sums[l + 1])); } stack.push(i); } while (!stack.isEmpty()) { cur = nums[stack.pop()]; l = stack.isEmpty() ? -1 : stack.peek(); r = n; max = Math.max(max, cur * (sums[r] - sums[l + 1])); } return max; } }
7.子数组最小值之和（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]。 最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。
思路： 这道题的本质在于找到数组中的每一个数作为最小值的范围，比如对于某个数nums[i]能够最小值以这种形式表示：左边连续m个数比nums[i]大，右边连续n个数比nums[i]大。
其实就是找以每个数左边和右边的最小值，中间的数一定都是大于当前这个数的（已经出栈）根据下标计算出这两个范围，根据上述公式计算即可。注意，可以在尾部添加0，保证剩余元素可以被弹出计算。
注意：在进行计算时，先将每个元素转成long型再计算，否则最后一个测试用例过不了。
代码：
private long mod = 1000000007; public int sumSubarrayMins(int[] arr) { long ans = 0; int n = arr.length; arr = Arrays.copyOf(arr, n + 1); arr[n] = 0; Deque<Integer> stack = new LinkedList<>(); for (int i = 0; i <= n; i++) { while (!stack.isEmpty() && arr[i] <= arr[stack.peek()]) { // 每个栈顶元素作为最小值 int index = stack.pop(); int lMin = !stack.isEmpty() ? stack.peek() : -1; int M = index - lMin - 1; int N = i - index - 1; ans += ((long)arr[index] * (M + 1) * (N + 1)) % mod; } stack.push(i); } return (int)(ans % mod); }
8.每日温度（739-中）
题目描述：请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
示例：
给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]， 你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
思路： 本题显然是计算当前元素与后边第一个比他大的元素距离，单调栈的典型性应用。
- 当前元素小于等于栈顶元素，入栈
- 当前元素大于栈顶元素，出栈，计算此时栈顶元素与下一个最大元素即当前元素的距离
注意：本题栈内元素可以不用出栈。
代码：
public int[] dailyTemperatures(int[] temperatures) { // 维护：从栈顶到栈底严格递增 Deque<Integer> stack = new LinkedList<>(); int n = temperatures.length; int[] ans = new int[n]; for (int i = 0; i < n; i++) { while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) { int peak = stack.pop(); ans[peak] = i - peak; } stack.push(i); } return ans; }
