单调栈
宝藏勘探
问题： 在一个从 0 到 n 的数轴上，每个位置有一个宝藏辐射值。两位勘探员正在勘探宝藏，勘探过的位置中的最大值和最小值之差代表整块数轴地的辐射值，能反映这块地方的宝藏可能性。两位勘探员 分别从数轴的两侧相向而行，但是他们之间有矛盾，不愿意隔得太近，两位勘探员中间只剩 k 个单位长度时，就会停止前进。目前不知道两位勘探员谁先出发，只知道他们各自从两端相向而行向中间靠拢，中间相隔 k 个位置的时候停止勘探。问这块数轴地可能最小的宝藏辐射值是多少？
答案： 经典的单调队列问题，这题解法有很多种，比如优先队列+延迟删除（力扣例题）、RMQ等等。由于这题一定是去掉中间的值，停止勘探区域移动过程中，可以将数组分为前部分和后部分，前部分可以边移动边更新前部分最大最小值，后部分则可以先按照前部分的计算方法倒着更新，将他们预处理然后更新答案即可。代码用单调队列写:
public static int minRadiationValue(int[] radiation, int n, int k) {
// 存储左侧最小辐射值的数组
int[] lmin = new int[n + 2];
// 存储右侧最小辐射值的数组
int[] rmin = new int[n + 2];
// 存储左侧最大辐射值的数组
int[] lmax = new int[n + 2];
// 存储右侧最大辐射值的数组
int[] rmax = new int[n + 2];
// 存储最终结果，初始化为最大整数
int result = Integer.MAX_VALUE;
// 初始化左侧最小辐射值数组的第一个元素为最大整数
lmin[0] = Integer.MAX_VALUE;
// 初始化右侧最小辐射值数组的最后一个元素为最大整数
rmin[n + 1] = Integer.MAX_VALUE;
// 从左到右遍历，更新左侧最小和最大辐射值数组
for (int i = 1; i <= n; i++) {
lmin[i] = Math.min(lmin[i - 1], radiation[i]);
lmax[i] = Math.max(lmax[i - 1], radiation[i]);
}
// 从右到左遍历，更新右侧最小和最大辐射值数组
for (int i = n; i >= 1; i--) {
rmin[i] = Math.min(rmin[i + 1], radiation[i]);
rmax[i] = Math.max(rmax[i + 1], radiation[i]);
}
// 遍历可能的范围，计算最小的宝藏辐射值
for (int i = 1; i <= (n-k); i++) {
result = Math.min(result, Math.max(lmax[i - 1], rmax[i + k]) - Math.min(lmin[i - 1], rmin[i + k]));
}
return result;
}
public static void main(String[] args) {
int[] radiation = {1, 3, 5, 2, 4, 7, 6};
int n = radiation.length - 1;
int k = 2;
System.out.println("最小的宝藏辐射值是: " + minRadiationValue(radiation, n, k));
}
739. 每日温度
请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] res = new int[temperatures.length];
Deque<Integer> deque = new LinkedList<>();
deque.offer(0);
for(int i = 1; i < temperatures.length; i++){
while(!deque.isEmpty() && temperatures[deque.peekLast()] < temperatures[i]){//保证栈顶元素是最大的，且是单调递减的
int temp = deque.pollLast();
res[temp] = i - temp;
}
deque.offer(i);
}
return res;
}
}
96.下一个更大元素 I
给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
解答：
//单调栈
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[] res = new int[nums1.length];
Deque<Integer> deque = new LinkedList<>();
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums1.length; i++){
map.put(nums1[i], i); // 存放nums1中数字的下标
}
Arrays.fill(res, -1); // 初始化res为-1
for(int i = 0; i < nums2.length; i++){
while(!deque.isEmpty() && nums2[i] > nums2[deque.peekLast()]){
int pre = deque.pollLast();
if(map.containsKey(nums2[pre])){
res[map.get(nums2[pre])] = nums2[i];
}
}
deque.offer(i);
}
return res;
}
}
//解2：
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[] res = new int[nums1.length];
Deque<Integer> deque = new LinkedList<>();
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums1.length; i++){
map.put(nums1[i], i); // 存放nums1中数字的下标
}
Arrays.fill(res, -1); // 初始化res为-1
for(int i = 0; i < nums2.length; i++){
while(!deque.isEmpty() && nums2[i] > nums2[deque.peekLast()]){
int pre = deque.pollLast();
if(map.containsKey(nums2[pre])){
res[map.get(nums2[pre])] = nums2[i];
}
}
deque.offer(i);
}
return res;
}
}
503.下一个更大元素II
给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
解答：
//单调栈
class Solution {
public int[] nextGreaterElements(int[] nums) {
int[] res = new int[nums.length];
Deque<Integer> deque = new LinkedList<>();
int cnt = 2;
Arrays.fill(res, -1);
while(cnt-- != 0){
for(int i = 0; i < nums.length; i++){
while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]){
int temp = deque.pollLast();
res[temp] = nums[i];
}
deque.offer(i);
}
}
return res;
}
}
//数组
public class Solution {
public int[] nextGreaterElements(int[] nums) {
int[] res = new int[nums.length];
for(int i = 0; i < nums.length; i++){
boolean flag = false;
int j = (i+1) % nums.length;
while(j !=i){
if(nums[j] > nums[i]){
res[i] = nums[j];
flag = true;
break;
}
j = (j+1) % nums.length;
}
if(!flag) res[i] = -1;
}
return res;
}
}
42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
解答：
//双指针
class Solution {
public int trap(int[] height) {
int res = 0;
int l = 0;
int r = height.length - 1;
int lmax = 0;
int rmax = 0;
while (l < r) {
lmax = Math.max(height[l], lmax);
rmax = Math.max(height[r], rmax);
if(lmax < rmax){
res += lmax - height[l];
l++;
}else{
res += rmax - height[r];
r--;
}
}
return res;
}
}
//单调栈
class Solution {
public int trap(int[] height) {
if(height.length < 3) return 0;
int res = 0;
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < height.length; i++) {
while (!deque.isEmpty() && height[i] > height[deque.peek()]) {
int bottom = deque.pop();
int hold = 0;
if (!deque.isEmpty()) {
int width = i - deque.peek() - 1;// 宽度
hold = (Math.min(height[deque.peek()], height[i]) - height[bottom]) * width;
}
res += hold;
}
deque.push(i);
}
return res;
}
}
84.柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
解答：
//单调栈
class Solution {
public int largestRectangleArea(int[] heights) {
int res = 0;
Deque<Integer> deque = new LinkedList<>();
int[] newheights = new int[heights.length + 2];
System.arraycopy(heights, 0, newheights, 1, heights.length);
heights = newheights;
deque.push(0);
for (int i = 1; i < heights.length; i++) {
while(!deque.isEmpty() && heights[i] < heights[deque.peek()]){
int mid = deque.pop();
int left = deque.peek();
int right = i;
res = Math.max(res, (right - left - 1) * heights[mid]); //(right - left - 1)表示不包含两端（left和right）的矩形的宽度，heights[mid]表示矩形的高度
}
deque.push(i);
}
return res;
}
}