739. 每日温度
问题描述
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]
提示：
1 <= temperatures.length <= 10530 <= temperatures[i] <= 100
代码实现
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
Stack<Integer> stack = new Stack<>(); // 辅助单调递增栈，存储数组元素下标
int[] res = new int[temperatures.length]; // 保存结果
for (int i = 0; i < temperatures.length; i++) {
// 保持单调递增栈
while (!stack.empty() && temperatures[stack.peek()] < temperatures[i]) { // 当前下标的元素比栈顶下标的元素大
Integer item = stack.pop(); // 弹出栈顶下标
res[item] = i - item; // 更新结果
}
stack.push(i);
}
return res;
}
}
踩坑点
无
496. 下一个更大元素 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] 是如上所述的 下一个更大元素 。
示例 1：
输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
示例 2：
输入：nums1 = [2,4], nums2 = [1,2,3,4].
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
- 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。
提示：
1 <= nums1.length <= nums2.length <= 10000 <= nums1[i], nums2[i] <= 104nums1和nums2中所有整数 互不相同nums1中的所有整数同样出现在nums2中
代码实现
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
// 辅助哈希表，记录nums1中的元素及其下标
Map<Integer, Integer> map = new HashMap<>(nums1.length);
for (int i = 0; i < nums1.length; i++) {
map.put(nums1[i], i);
}
Stack<Integer> stack = new Stack<>(); // 辅助单调栈
int[] ans = new int[nums1.length]; // 保存结果
Arrays.fill(ans, -1); // ans数组初始化-1
for (int i = 0; i < nums2.length; i++) { // 遍历nums2数组
// 维持单调栈，保持从栈底到栈顶下标对应的元素单调递减
while (!stack.empty() && nums2[stack.peek()] < nums2[i]){
Integer item = stack.pop(); // 弹出栈顶下标
if (map.containsKey(nums2[item])){ // nums[i]在nums1中存在
ans[map.get(nums2[item])] = nums2[i]; // 更新ans数组
}
}
// 当前元素下标入栈
stack.push(i);
}
return ans;
}
}
踩坑点
无
下一个更大元素 II
问题描述
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
示例 1:
输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
示例 2:
输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]
提示:
1 <= nums.length <= 104-109 <= nums[i] <= 109
代码实现
class Solution {
public int[] nextGreaterElements(int[] nums) {
int n = nums.length; // nums数组长度
Stack<Integer> stack = new Stack<>(); // 辅助单调栈
int[] ans = new int[n]; // 保存结果
Arrays.fill(ans, -1); // ans数组初始化-1
for (int i = 0; i < 2 * n; i++) { // 遍历nums2数组
// 维持单调栈，保持从栈底到栈顶下标对应的元素单调递减
while (!stack.empty() && nums[stack.peek() % n] < nums[i%n]) {
Integer item = stack.pop()% n; // 弹出栈顶下标
ans[item] = nums[i % n]; // 更新ans数组
}
// 当前元素下标入栈
stack.push(i);
}
return ans;
}
}
踩坑点
循环数组可以用%运算来降低难度
42. 接雨水
问题描述
给定 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 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
提示：
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
代码实现
单调栈
class Solution {
public int trap(int[] height) {
int res = 0; // 记录最终结果
Stack<Integer> stack = new Stack<>(); // 辅助单调栈（从栈底到栈顶递减），存储下标
for (int i = 0; i < height.length; i++) {
while (!stack.empty()) {
Integer mid = stack.peek(); // 获取栈顶下标
if (height[i] >= height[mid]) { // 当前下标对应元素大于等于栈顶下标对应元素
stack.pop();
if (!stack.empty()) { // 形成了中间低两边高的凹槽
Integer left = stack.peek();
int h = Math.min(height[i], height[left]) - height[mid]; // 高度
int w = i - left - 1; // 宽度，范围区间：[left+1,i-1]
res += h * w; // 累加求和
}
} else if (height[i] == height[mid]) {
stack.pop();
} else { // 结束内层while循环
break;
}
}
stack.push(i); // 当前下标入栈
}
return res;
}
}
双指针
class Solution {
public int trap(int[] height) {
int n = height.length;
int[] left = new int[n]; // 记录下标区间1~n-2的元素左边的最高柱
int[] right = new int[n]; // 记录下标区间1~n-2的元素右边的最高柱
left[0] = height[0];
right[n - 1] = height[n - 1]; // 赋初值
for (int i = 1; i < n - 1; i++) { // 左右边界必不可能形成凹槽去接雨水
left[i] = Math.max(left[i - 1], height[i]); // left[i]记录[0,i]范围内的最高的柱子
int j = n - i - 1;
right[j] = Math.max(right[j + 1], height[j]); // right[j]记录[j,n)范围内的最高的柱子
}
int res = 0; // 雨水数量
for (int i = 1; i < n - 1; i++) { // 左右边界必不可能形成凹槽去接雨水
res += Math.min(left[i], right[i]) - height[i];
}
return res;
}
}
踩坑点
无
84. 柱状图中最大的矩形
问题描述
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4]
输出： 4
提示：
1 <= heights.length <=1050 <= heights[i] <= 104
代码实现
class Solution {
/**
* 这题与接雨水不同的地方在于：
* 接雨水使用的是从栈底到栈顶递减的单调栈，且只有形成凹槽才能进行累加，heights单调递增或者单调递减时结果为0；
* 本题使用的是从栈底到栈顶递增的单调栈，这样到要比较插入的元素小于栈顶元素时，就会进行一次比较
* 但不同于接雨水，即使是heights单调递增或者单调递减，也需要进行计算更新最大矩形面积，所以在原数组首尾插入0形成新数组
*/
public int largestRectangleArea(int[] heights) {
int[] newHeight = new int[heights.length + 2];
// 首尾默认就插入0，然后拷贝原数组
System.arraycopy(heights, 0, newHeight, 1, heights.length);
Stack<Integer> stack = new Stack<>(); // 辅助栈，存储下标
int res = 0; // 记录最终结果
for (int i = 0; i < newHeight.length; i++) { // 遍历新数组
while (!stack.empty()) {
Integer mid = stack.peek();
if (newHeight[mid] > newHeight[i]) { // 栈顶元素大于当前元素
stack.pop();
if (!stack.empty()) {
// 新的栈顶元素就是原栈顶元素左边的第一个比它小的
Integer left = stack.peek();
int h = newHeight[mid]; // 高度
int w = i - left - 1; // 宽度[left+1,i-1]
res = Math.max(res, h * w);
}
} else if (newHeight[mid] == newHeight[i]) {
// 移除栈顶元素，避免重复计算（不移除对结果没影响，会多计算一次）
stack.pop();
break; // 结束内层循环
} else {
break;
}
}
stack.push(i); // 入栈
}
return res;
}
}
踩坑点
无
![[SystemVerilog]常见设计模式/实践](https://img-home.csdnimg.cn/images/20230724024159.png?origin_url=https%3A%2F%2Fsystemverilog.dev%2Fimages%2F04%2Fwishbone_diagram.svg&pos_id=HJ7nmITM)
