通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为O(n)。
单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是整个数组只需要遍历一次。
栈中存放什么？下标！！
1. 每日温度
题目描述
题目链接
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
解题思路
- 要求左边第一个比自己大的元素的位置，使用一个递减的单调栈。
- 当碰到小于等于栈顶的元素时就入栈。
- 当碰到大于栈顶的元素时，循环出栈并记录答案，直到栈顶元素大于等于当前元素，将当前元素入栈。
代码
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
Deque<Integer> stack = new LinkedList<>(); //存放下标
int[] ans = new int[temperatures.length];
stack.push(0);
for(int i=1; i<temperatures.length; i++) {
while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
ans[stack.peek()] = i - stack.peek();
stack.pop();
}
stack.push(i);
}
return ans;
}
}
2. 下一个更大元素I
题目描述
题目链接
nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
解题思路
-
找到nums1在nums2中对应的元素的下一个更大元素，其实还是找nums2中元素的下一个更大元素。
-
用单调栈找nums2的下一个更大元素，并对应到nums1中元素的下标即可。
-
使用HashMap存nums1[i]:i
代码
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[] ans = new int[nums1.length];
Arrays.fill(ans, -1);
//存放nums1[i]:i
HashMap<Integer, Integer> map = new HashMap<>();
for(int i=0; i<nums1.length; i++) {
map.put(nums1[i], i);
}
Deque<Integer> stack = new LinkedList<>();
stack.push(0);
for(int i=1; i<nums2.length; i++) {
while(!stack.isEmpty() && nums2[stack.peek()] < nums2[i]) {
int key = nums2[stack.peek()];
if(map.containsKey(key)) {
ans[map.get(key)] = nums2[i];
}
stack.pop();
}
stack.push(i);
}
return ans;
}
}
3. 下一个更大元素II
题目描述
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
解题思路
- 循环数组的下一个更大元素，其实把数组再遍历一遍就行了，就相当于拼接两个数组。
代码
class Solution {
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
Arrays.fill(ans, -1);
Deque<Integer> stack = new LinkedList<>();
stack.push(0);
for(int i=1; i<n*2; i++) {
while(!stack.isEmpty() && nums[stack.peek()%n] < nums[i%n]) {
ans[stack.peek()%n] = nums[i%n];
stack.pop();
}
stack.push(i%n);
}
return ans;
}
}
4. 接雨水
题目描述
题目链接
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
解题思路
方法1：双指针优化
-
分别考虑每一列能装多少雨水
-
每一列能装的雨水的高度取决于该列 左边最高的柱子和右边最高的柱子 中最矮的那个
-
如何求左边最高的柱子的高度和右边最高的柱子的高度？动态规划，
lHeight[i] = max(lHeight[i-1], height[i-1])，右边类似。 -
注意：最两边的柱子不能装水
代码
class Solution {
public int trap(int[] height) {
int n = height.length;
int[] lHeight = new int[n];
int[] rHeight = new int[n];
lHeight[0] = 0;
for(int i=1; i<n; i++) {
lHeight[i] = Math.max(lHeight[i-1], height[i-1]);
}
rHeight[n-1] = 0;
for(int i=n-2; i>=0; i--) {
rHeight[i] = Math.max(rHeight[i+1], height[i+1]);
}
int ans = 0;
for(int i=1; i<n-1; i++) {
int deta = Math.min(lHeight[i], rHeight[i]) - height[i];
if(deta > 0) {
ans += deta;
}
}
return ans;
}
}
方法2：单调栈（还是不太懂）
-
对于当前柱子，只有在找到了下一个比它高的柱子时，这两个柱子中间才能装水。因此变成了单调栈能解决的问题。
-
单调栈是递减的，因为一旦发现添加的柱子高度大于栈头元素了，此时就出现凹槽了，栈头元素就是凹槽底部的柱子，栈头第二个元素就是凹槽左边的柱子，而添加的元素就是凹槽右边的柱子。
-
这时，是一层一层的计算的。
代码
class Solution {
public int trap(int[] height) {
Deque<Integer> stack = new LinkedList<>();
stack.push(0);
int ans = 0;
for(int i=1; i<height.length; i++) {
if(height[i] < height[stack.peek()]) {
stack.push(i);
} else if(height[i] == height[stack.peek()]) {
stack.pop();
stack.push(i);
} else { //凹槽的右边柱子
while(!stack.isEmpty() && height[i] > height[stack.peek()]) {
int mid = stack.peek(); //凹槽
stack.pop();
if(!stack.isEmpty()) { //凹槽的左边柱子
int h = Math.min(height[stack.peek()], height[i]) - height[mid];
int w = i - stack.peek() - 1;
ans += h * w;
}
}
stack.push(i);
}
}
return ans;
}
}
5. 柱状图中最大的矩形
题目描述
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
解题思路（代码随想录的题解没看懂）
-
找到每个柱子以自己的高度能扩展的最大面积中的最大值即可
-
对于每个柱子, 以它的高度能扩展的最大面积，需要找左边第一个比它小的和右边第一个比它小的->单调栈
代码
class Solution {
//对于每个柱子, 以它的高度能扩展的最大面积
//需要找左边第一个比它小的和右边第一个比它小的
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int[] lHeight = new int[n];
int[] rHeight = new int[n];
Arrays.fill(lHeight, -1);
Arrays.fill(rHeight, -1);
//找左边第一个比它小的
Deque<Integer> stack = new LinkedList<>();
stack.push(n-1);
for(int i=n-2; i>=0; i--) {
while(!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
lHeight[stack.peek()] = i;
stack.pop();
}
stack.push(i);
}
//找右边第一个比它小的
stack = new LinkedList<>();
stack.push(0);
for(int i=1; i<n; i++) {
while(!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
rHeight[stack.peek()] = i;
stack.pop();
}
stack.push(i);
}
//计算以每个柱子的高度为矩形高度的扩展面积
int ans = 0;
for(int i=0; i<n; i++) {
//area = (右边第一个比它矮的柱子的坐标 - 左边第一个比它矮的柱子的坐标 - 1) * 柱子高度
//当左边没有比它矮的柱子时，从-1开始计算
//当右边没有比它矮的柱子时，从n开始计算
int area = ((rHeight[i] == -1 ? n : rHeight[i]) - (lHeight[i] == -1 ? -1 : lHeight[i]) - 1) * heights[i];
ans = Math.max(ans, area);
}
return ans;
}
}