算法：【单调栈】
单调栈模板
常见模型：找出每个数左边离它最近的比它大/小的数
Deque<Integer> stack = new LinkedList<>();
for (int i = 0; i < n; i ++ ){
while (!stack.isEmpty( && check(stack.peek(), i)) {
// 业务逻辑
}
stack.push(i);
}1.接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 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 {
// 1.单调栈：维护一个栈底到栈顶单调递减的单调栈，这样每次弹出的数，小于当前数和下面的数，即满足可接雨水的部分
public int trap(int[] height) {
int ans = 0;
Deque<Integer> stack = new LinkedList<>();
int n = height.length;
for(int i=0; i<n; i++){
while(!stack.isEmpty() && height[i] > height[stack.peek()]){
int top = stack.pop();
if(stack.isEmpty())
break;
int left = stack.peek();
int curwidth = i-left-1;
int curheight = Math.min(height[i], height[left]) - height[top];
ans += curwidth * curheight;
}
stack.push(i);
}
return ans;
}
// 2.动态规划
// public int trap(int[] height) {
// int ans = 0;
// int n = height.length;
// if(n == 0)
// return ans;
// int leftmax[] = new int[n];
// leftmax[0] = height[0];
// for(int i=1; i<n; i++){
// leftmax[i] = Math.max(leftmax[i-1], height[i]);
// }
// int[] rightmax = new int[n];
// rightmax[n-1] = height[n-1];
// for(int i=n-2; i>=0; i--){
// rightmax[i] = Math.max(rightmax[i+1], height[i]);
// }
// for(int i=0; i<n; i++){
// ans += Math.min(leftmax[i], rightmax[i]) - height[i];
// }
// return ans;
// }
}2.和至少为 K 的最短子数组
返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。
如果没有和至少为 K 的非空子数组，返回 -1 。输入：A = [1], K = 1
输出：1
class Solution {
// 前缀和 + 变种单调栈结构（栈底到栈顶单调递增）
public int shortestSubarray(int[] nums, int k) {
int[] sum = new int[nums.length+1]; // 前缀和数组
for(int i=0; i<nums.length; i++){
sum[i+1] = sum[i] + nums[i];
}
int res = -1;
Deque<Integer> stack = new LinkedList<>();
for(int i=0; i<=nums.length; i++){
while(!stack.isEmpty() && sum[i] < sum[stack.peekLast()]){
stack.removeLast();
}
while(!stack.isEmpty()){
if(sum[i] - sum[stack.peekFirst()] >= k){
res = res == -1 ? i-stack.peekFirst() : Math.min(res,i-stack.peekFirst());
stack.removeFirst();
}else{
break;
}
}
if(sum[i] >= k){
res = res==-1?i+1:Math.min(res,i+1);
}
stack.addLast(i);
}
return res;
}
}3. 二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
输入: [1,6,3,2,5]
输出: false
思路：
- 后序遍历倒序： [ 根节点 | 右子树 | 左子树 ] 。类似 先序遍历的镜像 ，即先序遍历为 “根、左、右” 的顺序，而后序遍历的倒序为 “根、右、左” 顺序。
class Solution { public boolean verifyPostorder(int[] postorder) { Stack<Integer> stack = new Stack<>(); int root = Integer.MAX_VALUE; for(int i = postorder.length - 1; i >= 0; i--) { if(postorder[i] > root) return false; while(!stack.isEmpty() && stack.peek() > postorder[i]) root = stack.pop(); stack.add(postorder[i]); } return true; } }
4.最大矩形
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例1：
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。
class Solution {
public int maximalRectangle(char[][] matrix) {
if(matrix.length == 0 || matrix[0].length == 0)
return 0;
int[] height = new int[matrix[0].length];
int res = 0;
for(int i=0; i<matrix.length; i++){
for(int j=0; j<matrix[0].length; j++){
height[j] = matrix[i][j] == '0' ? height[j] = 0 : height[j]+1;
}
res = Math.max(res, process(height));
}
return res;
}
// 单调栈
public int process(int[] height){
if(height == null || height.length == 0)
return 0;
int res = 0;
Deque<Integer> stack = new LinkedList<>();
for(int i=0; i<height.length; i++){
while(!stack.isEmpty() && height[stack.peek()] >= height[i]){
int j = stack.pop();
int k = stack.isEmpty() ? -1 : stack.peek();
int width = i-k-1;
res = Math.max(res, width*height[j]);
}
stack.push(i);
}
int i = height.length;
while(!stack.isEmpty()){
int j = stack.pop();
int k = stack.isEmpty() ? -1 : stack.peek();
int width = i-k-1;
res = Math.max(res, width*height[j]);
}
return res;
}
}5.下一个更大元素 II
给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
注意事项：
注意到只遍历一次序列是不够的，例如序列 [2,3,1]，最后单调栈中将剩余 [3,1]，其中元素 [1] 的下一个更大元素还是不知道的。
一个朴素的思想是，我们可以把这个循环数组「拉直」，即复制该序列的前 n-1 个元素拼接在原序列的后面。这样我们就可以将这个新序列当作普通序列，用上文的方法来处理。
而在本题中，我们不需要显性地将该循环数组「拉直」，而只需要在处理时对下标取模即可。
class Solution {
// 单调栈
public int[] nextGreaterElements(int[] nums) {
Deque<Integer> stack = new LinkedList<>();
int[] res = new int[nums.length];
int n = nums.length;
Arrays.fill(res, -1);
for(int i=0; i<n*2-1; i++){
while(!stack.isEmpty() && nums[i%n] > nums[stack.peek()]){
int j =a stack.pop();
res[j] = nums[i%n];
}
stack.push(i%n);
}
return res;
}
}6.132 模式
class Solution {
// 1.单调栈
public boolean find132pattern(int[] nums) {
if(nums.length < 3)
return false;
Deque<Integer> stack = new LinkedList<>();
int k = -1;
for(int i=nums.length-1; i>=0; i--){
if(k>-1 && nums[k]>nums[i])
return true;
while(!stack.isEmpty() && nums[i] > nums[stack.peek()]){
k = stack.pop();
}
stack.push(i);
}
return false;
}
}
阿里云工作强度 710人发布
查看4道真题和解析