文章目录

• 单调栈
• • 1.每日温度
  • 2.下一个更大元素 I
  • 3.下一个更大元素II
  • 4. 接雨水
  • 5.柱状图中最大的矩形

单调栈

单调栈基础知识回顾：单调栈与单调队列_塔塔开!!!的博客-CSDN博客_单调栈 单调队列

单调栈一般模板：

int[] stk = new int[N] //Stack stk;
int tt = 0;// 模板1....
for(int i = 0; i < nums.size(); i++){while(tt != 0 && stk[tt] > nums[i]){tt --;// 出栈.....// 业务处理        }stk[++ tt] = nums[i];// 数/下标1入栈
}// 模板2....
for(int i = 0; i < nums.size(); i++){while(tt != 0 && stk[tt] <= nums[i]) tt --;// 出栈if(tt == 0){.....}else .....// 业务：（记录左边/右边 第一个比它小/大的数等等业务）stk[++ tt] = nums[i];// 数/下标入栈
}

1.每日温度

题目链接：739. 每日温度 - 力扣（LeetCode）

Code

class Solution {/**思路：从右往左遍历 实现单调递减栈，记录当前每一个数 右边第一个大于它的数的位置（单调递减栈）*/int N = 100010;int[] stk = new int[N];int tt;int[] pos = new int[N];public int[] dailyTemperatures(int[] a) {int n = a.length;for(int i = n - 1; i >= 0; i --){while(tt != 0 && a[stk[tt]] <= a[i]) tt --;if(tt == 0) pos[i] = 0;else pos[i] = stk[tt];// 记录右边大于它的第一个数的位置stk[++ tt] = i;}int[] res = new int[n];for(int i = 0; i < n; i ++){if(pos[i] == 0){res[i] = 0;}else {res[i] = pos[i] - i;// 计算位于右边的第几个}}return res;}
}

2.下一个更大元素 I

题目链接：496. 下一个更大元素 I - 力扣（LeetCode）

思路一：枚举 + 哈希表

我们用哈希表来记录，nums2[]中nums1[i]出现的位置，然后我们两重遍历，一重循环遍历nums1，二重循环从nums1[i]对应在nums2的位置j开始遍历，然后找到第一个大于nums1[i]的mums2[j]，找到则直接跳出，否则不存在。

Code

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {Map mp = new HashMap<>();int n = nums1.length;int m = nums2.length;int[] res = new int[n];int cnt = 0;for(int i = 0; i < m; i ++) mp.put(nums2[i], i);for(int i = 0; i < n; i ++){boolean f = false;for(int j = mp.get(nums1[i]); j < m; j ++){if(nums2[j] > nums1[i]){res[cnt ++] = nums2[j];f = true;break;}}if(!f) res[cnt ++] = -1;}return res;}
}

思路二：单调栈 + 哈希表——跟每日温度一样求的是右边第一个大于它的数。（从右往左）遍历nums2，单调栈求得右边第一个大于它的数，然后用哈希表记录下来，最后我们在遍历nums1即可。

Code

class Solution {int N = 1010;int[] stk = new int[N];int tt = 0;public int[] nextGreaterElement(int[] nums1, int[] nums2) {int n = nums1.length;int m = nums2.length;// 从右往左遍历 找出右边大于它的 第一个数Map mp = new HashMap<>();for(int i = m - 1; i >= 0; i --){while(tt != 0 && stk[tt] <= nums2[i]) tt --;if(tt == 0) mp.put(nums2[i], -1);else mp.put(nums2[i], stk[tt]);stk[++ tt] = nums2[i];}int[] res = new int[n];for(int i = 0; i < n; i ++){res[i] = mp.get(nums1[i]);}return res;}
}

3.下一个更大元素II

题目链接：503. 下一个更大元素 II - 力扣（LeetCode）

思路：从右往左遍历 实现单调递减栈，记录当前每一个数 右边第一个大于它的数的位置，与上一题不同的是，本题的数组是环形的。
我们可以将原数组扩展为两倍得长度 就相当于我们进行了下一个更大元素I的两次操作 —— （将循环数组变为链状）（实在不理解就手动模拟就好了）

1 2 1 —> 1 2 1 1 2 1

将环变为链，相当于我们可以考虑到当前数的左边的数（也就是当前数在环中的向右的下一个元素（其实就是在它的左边））

Code

class Solution {int N = 100010;int[] stk = new int[N];int tt;public int[] nextGreaterElements(int[] a) {int n = a.length;int[] res = new int[n];int cnt = 0;for(int i = 2 * n - 1; i >= 0; i --){int x = a[i % n];int idx = i % n;while(tt != 0 && stk[tt] <= x) tt --;if(tt == 0) res[idx] = -1;else res[idx] = stk[tt];// 记录右边大于它的第一个数的位置stk[++ tt] = x;// 入栈}return res;}
}

4. 接雨水

题目链接：

Code

思路一：动态规划

状态表示：

• left[i]：表示柱子i左侧的最高柱子高度为left[i]
• right[i]：表示柱子i右侧的最高柱子高度为right[i]

状态计算：

• left[i] = max(left[i - 1], heigth[i - 1])
• right[i] = max(right[i + 1], heigth[i + 1])

初始化：

• left[0] = 0

• rigth[n - 1] = 0

Code

class Solution {public int trap(int[] height) {int n = height.length;int[] left = new int[n + 10];int[] right = new int[n + 10];// 初始化// Arrays.fill(left, 0);// Arrays.fill(right, 0);left[0] = 0;right[n - 1] = 0;// 求每根柱子左右两边的最大高度for(int i = 1; i < n; i ++){left[i] = Math.max(left[i - 1], height[i - 1]);// 有点DP的意味}for(int i = n - 2; i >= 0; i --){right[i] = Math.max(right[i + 1], height[i + 1]);}// 求雨水面积int res = 0;for(int i = 0; i < n; i ++){// 计算每一个位置可以接收的水量int minH = Math.min(left[i], right[i]);if(minH > height[i]){res += (minH - height[i]);}    }return res;}
}

这种解法的积水量是一列一列求取的！

思路二：单调栈

单调递减栈

• 理解题目，参考图，注意题目的性质，当后面的柱子高度比前面的低时，是无法接雨水的
• 当找到一根比前面高的柱子，就可以计算接到的雨水，所以使用单调递减

这种解法面积是横向求取的！

Code

/**单调栈（递减栈）：当遇到大于栈顶元素的柱子（说明可以形成水洼），然后再获取当前洼的高度(栈顶元素就是当前元素)和左边最低的高度（栈顶元素的下一个元素（大于等于当前高度）），即可计算面积（横向的）： res += h（min(L, R) - heigth[cur]） * w，否则元素下标入栈*/
class Solution {int[] stk = new int[2 * 10000 + 10];int tt = 0;public int trap(int[] height) {int n = height.length;int res = 0;for(int i = 0; i < n; i ++){while(tt != 0 && height[stk[tt]] < height[i]){int cur = stk[tt --];if(tt == 0){// 栈为空时 就breakbreak;}int l = stk[tt];int r = i;int h = Math.min(height[l], height[r]) - height[cur];res += h * (r - l - 1);}stk[++ tt] = i;}return res;}
}

5.柱状图中最大的矩形

题目链接：84. 柱状图中最大的矩形 - 力扣（LeetCode）

对于每一个位置我们怎么求它所能构成的最大矩阵呢？首先，要想找到第 i 位置最大面积是什么？

是以i 为中心（矩形的高度由height[i]决定），要使得面积最大，那么就要找到最大宽度，如何寻找最大宽度是关键：

• 向左找第一个小于 heights[i] 的位置 left_i（left_i后面的位置到i（(left_i,i]）都是可以参与以heigth[i]为高度矩形的构成）；

• 向右找第一个小于于 heights[i] 的位置 right_i（ right_i前面的位置到（[i, right_i)）i都是可以参与以heigth[i]为高度矩形的构成）

即最大面积为 heights[i] * (right_i - left_i -1)

Code

/**思路：单调栈去求每一个位置i 左右两边第一个小于当前i位置高度的位置, 当前位置的最大矩形 s = (R-L-1) * h[i]记录两个特殊临界值：当找左边时，栈为空（说明无小于它的，都可以取，我们将其位置即为-1 l[i] = -1）当找右边时，栈为空（说明无小于它的，都可以取，我们将其位置即为n r[i] = n）我们开两个数组记录每一个位置 左右两边第一个小于它的位置，然后枚举计算最大值即可*//**单调递增栈：求左/右边第一个小于它的数的位置（顺序/逆序遍历）*/class Solution {int[] stk = new int[100010];int tt = 0;int[] l = new int[100010];int[] r = new int[100010];public int largestRectangleArea(int[] heights) {int n = heights.length;for(int i = 0; i < n; i ++){while(tt != 0 && heights[stk[tt]] >= heights[i]) tt --;if(tt == 0) l[i] = -1;// 我们认为zuo边没有最小时指定为位置-1else l[i] = stk[tt];stk[++ tt] = i;// 记录左边第一个小于它的位置}Arrays.fill(stk, 0);tt = 0;for(int i = n - 1; i >= 0; i --){while(tt != 0 && heights[stk[tt]] >= heights[i]) tt --;if(tt == 0) r[i] = n;// 我们认为右边没有最小时指定为位置nelse r[i] = stk[tt];stk[++ tt] = i;}// for(int i = 0; i < n; i ++){//     System.out.print(l[i] + " ");// }// System.out.println();// for(int i = 0; i < n; i ++){//     System.out.print(r[i] + " ");// }        int res = 0;for(int i = 0; i < n; i ++){res = Math.max(res, (r[i] - l[i] - 1) * heights[i]);}return res;}
}