单调栈
1、每日温度 739
https://leetcode.cn/problems/daily-temperatures/description/
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
1
2
| 输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
|
示例 2:
1
2
| 输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
|
示例 3:
1
2
| 输入: temperatures = [30,60,90]
输出: [1,1,0]
|
提示：
- 1 <= temperatures.length <= 105`
30 <= temperatures[i] <= 100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| import java.util.ArrayDeque;
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int len = temperatures.length;
int[] result = new int[len];
ArrayDeque<Integer> stack = new ArrayDeque<>();
stack.push(0);
for (int i = 1; i < len; i++) {
if (temperatures[i] <= temperatures[stack.peek()]){
stack.push(i);
} else {
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
result[stack.peek()] = i - stack.peek();
stack.pop();
}
stack.push(i);
}
}
return result;
}
}
|
2、下一个更大元素I 496
https://leetcode.cn/problems/next-greater-element-i/description/
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：
1
2
3
4
5
6
| 输入：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：
1
2
3
4
5
| 输入：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 中
进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| import java.util.ArrayDeque;
import java.util.HashMap;
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
HashMap<Integer,Integer> hashmap = new HashMap<>();
ArrayDeque<Integer> stack = new ArrayDeque<>();
stack.push(0);
for (int i = 1; i < len2; i++) {
if (nums2[i] <= nums2[stack.peek()]) {
stack.push(i);
}else {
while(!stack.isEmpty() && nums2[i] > nums2[stack.peek()]){
hashmap.put(nums2[stack.peek()],nums2[i]);
stack.pop();
}
stack.push(i);
}
}
int[] result = new int[len1];
for (int i = 0; i < len1; i++) {
result[i] = hashmap.getOrDefault(nums1[i], -1);
}
return result;
}
}
|
3、下一个更大元素II 503
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
示例 1:
1
2
3
4
5
| 输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
|
示例 2:
1
2
| 输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]
|
提示:
1 <= nums.length <= 104-109 <= nums[i] <= 109
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| import java.util.ArrayDeque;
import java.util.Arrays;
class Solution {
public int[] nextGreaterElements(int[] nums) {
int len = nums.length;
ArrayDeque <Integer> stack = new ArrayDeque<>();
stack.push(0);
int[] result = new int[len];
Arrays.fill(result, -1);
for (int i = 1; i < len * 2; i++) {
while(!stack.isEmpty() && nums[i % len] > nums[stack.peek()]) {
result[stack.peek()] = nums[i%len];
stack.pop();
}
stack.push(i%len);
}
return result;
}
}
|
4、接雨水 42
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
https://leetcode.cn/problems/trapping-rain-water/description/
示例 1：
1
2
3
| 输入：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：
1
2
| 输入：height = [4,2,0,3,2,5]
输出：9
|
提示：
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| import java.util.ArrayDeque;
class Solution {
public int trap(int[] height) {
int len = height.length;
int result = 0;
ArrayDeque<Integer> stack = new ArrayDeque<>();
stack.push(0);
for (int i = 1; i < len; i++) {
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int curHeight = height[stack.peek()];
stack.pop();
if(!stack.isEmpty()) {
int secondHeight = height[stack.peek()];
int resultHeight = Math.min(height[i],secondHeight) - curHeight;
result += resultHeight * (i-stack.peek()-1);
}
}
stack.push(i);
}
return result;
}
}
|
5、 柱状图中最大的矩形 84
https://leetcode.cn/problems/largest-rectangle-in-histogram/description/
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
1
2
3
| 输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
|
示例 2：
1
2
| 输入： heights = [2,4]
输出： 4
|
提示：
1 <= heights.length <=1050 <= heights[i] <= 104
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| import java.util.ArrayDeque;
class Solution {
public int largestRectangleArea(int[] heights) {
int[] newheights = new int[heights.length + 2];
System.arraycopy(heights, 0, newheights, 1, heights.length);
int len = newheights.length;
ArrayDeque<Integer> stack = new ArrayDeque<>();
int result = 0;
stack.push(0);
for (int i = 1; i < len; i++) {
while (!stack.isEmpty() && newheights[i] < newheights[stack.peek()]) {
int height = newheights[stack.peek()];
stack.pop();
if (!stack.isEmpty()) {
int left = stack.peek();
result = Math.max(height*(i-left-1),result);
}
}
stack.push(i);
}
return result;
}
}
|