算法学习笔记（八）：单调栈
横看成岭侧成峰，引用灵神的话：他向远方望去，无法看到高山背后的矮山，只能看到一座座更高的山峰。
单调栈的两种写法：从左到右写法、从右到左写法，就学习其中一种吧，下面都是从左到右的写法
单调栈适用范围：需要找上一个更大(小)元素、下一个更大(小)元素。
1.每日温度
给定一个整数数组 temperatures，表示每天的温度，返回一个数组 answer，其中 answer[i]
是指对于第 i 天，下一个更高温度出现在几天后，如果气温在这之后都不会升高，用0代替
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
//单调栈，从左到右写法
//每个元素进栈，进栈之前和栈顶元素比较
//本题是找大，所以当前元素和栈顶比较 如果>栈顶
//表示当前温度就是栈顶的下一个更高温度，
//那么栈顶弹栈，继续和栈顶比较，一直到栈为空
//或者当前温度比栈顶小，则将当前元素入栈
//在弹栈的过程中，更新被弹栈的元素数据即可
//最后遍历栈，还留在栈里面的都是没有下一个更高温度的
LinkedList<Integer> stack = new LinkedList<>();
int[] ans = new int[temperatures.length];
for (int i = 0; i < temperatures.length; i++) {
int cur = temperatures[i];
while (!stack.isEmpty() && temperatures[stack.peek()] < cur) {
//之前没找到下一个更高温度的天数出栈 并更新值为当前天
int index = stack.poll();
ans[index] = i - index;
}
stack.push(i);
}
//因为没找到的用0来代替 初始化int[] 初始值就默认是0了
return ans;
}
}2.商品折扣后的最终价格
给你一个数组 prices，其中 prices[i] 是商店里第 i 件商品的价格
商店里正在进行促销活动，如果你要买第 i 件商品，那么你可以得到与 prices[j] 相等的折扣
其中 j 是满足 j > 1 且 prices[j] <= prices[i] 的最小下标，如果没有满足条件的 j， 你将没有
任何折扣，请你返回一个数组，数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格
class Solution {
public int[] finalPrices(int[] prices) {
//其实就是找当前元素的下一个更小值，然后最终价格是当前-最小值
LinkedList<Integer> stack = new LinkedList<>();
int[] ans = new int[prices.length];
for (int i = 0; i < prices.length; i++) {
int cur = prices[i];
while (!stack.isEmpty() && cur <= prices[stack.peek()]) {
//当前比栈顶小的弹栈 否则入栈
int index = stack.poll();
ans[index] = prices[index] - cur;
}
stack.push(i);
}
while (!stack.isEmpty()) {
int top = stack.pop();
ans[top] = prices[top];
}
return ans;
}
}3.下一个更大的元素 I
nums1 中数字 x 的下一个更大元素 是指 x 在nums2 中对应位置右侧的第一个比 x大的元素
给你两个数组 nums1 和 nums2，下标从0开始，其中nums1是nums2的子集
对于每个0 <= i < nums1.length，找出满足 nums1[i] == nums[j]的下标 j，并且在nums2确定
nums2[j]的下一个更大元素，如果不存在下一个更大元素，那么则为-1
返回一个长度为nums1.length的数组ans作为答案
nums1和nums2元素都不重复
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Map<Integer, Integer> map = new HashMap<>();
int[] ans = new int[nums1.length];
Arrays.fill(ans, -1);
LinkedList<Integer> stack = new LinkedList<>();
//先将nums1元素用哈希存储位置关系
for (int i = 0; i < nums1.length; i++) {
map.put(nums1[i], i);
}
for (int i = 0; i < nums2.length; i++) {
int cur = nums2[i];
while (!stack.isEmpty() && cur > stack.peek()) {
int top = stack.poll();
ans[map.get(top)] = cur;
}
//只有在nums1中的元素才入栈
if (map.containsKey(cur)) {
stack.push(cur);
}
}
return ans;
// //两个数组的单调栈 想一下怎么写
// int[] arr = new int[nums1.length];
// LinkedList<Integer> stack = new LinkedList<>();
// //好像本之还是求nums2里面的每个元素的下一个更大的元素 是吧
// //先把nums2里面的每个元素的下一个更大元素算出来 然后遍历nums1
// //找到nums1的元素在nums2里面的位置 然后直接拿到算好的数据
// Map<Integer, Integer> map = new HashMap<>();
// for (int i = 0; i < nums2.length; i++) {
// int cur = nums2[i];
// while (!stack.isEmpty() && cur > nums2[stack.peek()]) {
// int top = stack.poll();
// map.put(nums2[top], cur);
// }
// stack.push(i);
// }
// while (!stack.isEmpty()) {
// map.put(nums2[stack.poll()], -1);
// }
// for (int i = 0; i < nums1.length; i++) {
// arr[i] = map.get(nums1[i]);
// }
// return arr;
}
}4.下一个更大元素II
给定一个循环数组 nums （nums[nums.length - 1]的下一个元素是 nums[0]），返回nums
中每个元素的下一个更大的元素
需要循环的搜索数组
class Solution {
public int[] nextGreaterElements(int[] nums) {
LinkedList<Integer> stack = new LinkedList<>();
int len = nums.length;
int[] ans = new int[len];
Arrays.fill(ans, -1); //默认全是-1 这样就不用翻译了
for (int i = 0; i < len * 2; i++) {
int cur = nums[i % len];
while (!stack.isEmpty() && cur > nums[stack.peek()]) {
int index = stack.pop();
ans[index] = cur;
}
stack.push(i % len);
}
return ans;
//学到了 这种循环数组遍历的方式
//可以复制一份原数组放到最右边
//比如[1,2,1] --> [1,2,1,1,2,1]
//这样最后一个1的下一个更大元素就是4%3=1
// for (int i = 0; i < nums.length; i++) {
// int cur = nums[i];
// while (!stack.isEmpty() && cur > nums[stack.peek()]) {
// int top = stack.pop();
// arr[top] = i;
// }
// stack.push(i);
// }
// //栈里面都是没找到的元素，需要在进行以下从头到当前遍历查找以下
// while (!stack.isEmpty()) {
// int cur = stack.pop();
// if (cur == 0) {
// arr[cur] = -1;
// continue;
// }
// for (int i = 0; i < cur; i++) {
// if (nums[i] > nums[cur]) {
// arr[cur] = i;
// break;
// }
// if (i == cur - 1) {
// arr[cur] = -1;
// }
// }
// }
// //翻译以下
// for (int i = 0; i < arr.length; i++) {
// int cur = arr[i];
// if (cur == -1) continue;
// arr[i] = nums[cur];
// }
// return arr;
}
}5.链表中的下一个更大的节点
给定一个长度为 n 的链表 head
对于列表中的每个节点，查找下一个更大节点的值，也就是说，对于每个节点，找到它旁边
的第一个节点的值，这个节点的值 严格大于 它的值
返回一个整数数组 answer，其中answer[i]是第i个(从1开始)的下一个更大的节点的值，如果
第i个节点没有下一个更大的节点，设置answer[i] = 0
class Solution {
public int[] nextLargerNodes(ListNode head) {
Map<Integer, Integer> map = new HashMap<>();
int index = 1;
ListNode curr = head;
while (curr != null) {
map.put(index++, curr.val);
curr = curr.next;
}
int[] ans = new int[map.size()];
LinkedList<Integer> stack = new LinkedList<>();
ListNode cur = head;
index = 1;
while (cur != null) {
int val = cur.val;
while (!stack.isEmpty() && val > map.get(stack.peek())) {
int top = stack.pop();
ans[top - 1] = val;
}
stack.push(index++);
cur = cur.next;
}
return ans;
}
}