【算法】单调栈每日温度接雨水

文章目录

例题
- 739. 每日温度
- 42. 接雨水
相关练习
- 1475. 商品折扣后的最终价格
- 901. 股票价格跨度
- 1019. 链表中的下一个更大节点
- 84. 柱状图中最大的矩形

单调栈【基础算法精讲 26】

例题

739. 每日温度

https://leetcode.cn/problems/daily-temperatures/description/
在这里插入图片描述

提示：

1 <= temperatures.length <= 10^5
30 <= temperatures[i] <= 100

class Solution {public int[] dailyTemperatures(int[] temperatures) {int n = temperatures.length;int[] ans = new int[n];Deque<Integer> stk = new ArrayDeque<>();for (int i = 0; i < n; ++i) {while (!stk.isEmpty() && temperatures[i] > temperatures[stk.peek()]) {int l = stk.pop();ans[l] = i - l;}stk.push(i);}return ans;}
}

42. 接雨水

https://leetcode.cn/problems/trapping-rain-water/
在这里插入图片描述

提示：

n == height.length
1 <= n <= 2 * 10^4
0 <= height[i] <= 10^5

每次计算的是一层。（还挺难理解的）

class Solution {public int trap(int[] height) {Deque<Integer> stk = new ArrayDeque<>();int ans = 0;for (int i = 0; i < height.length; ++i) {while (!stk.isEmpty() && height[i] > height[stk.peek()]) {int cur = stk.pop();if (!stk.isEmpty()) {int l = stk.peek();ans += (Math.min(height[i], height[l]) - height[cur]) * (i - l - 1);}}stk.push(i);}return ans;}
}

相关练习

1475. 商品折扣后的最终价格

https://leetcode.cn/problems/final-prices-with-a-special-discount-in-a-shop/description/

在这里插入图片描述
提示：
1 <= prices.length <= 500
1 <= prices[i] <= 10^3

class Solution {public int[] finalPrices(int[] prices) {int n = prices.length;int[] ans = new int[n];Arrays.setAll(ans, e -> prices[e]);Deque<Integer> stk = new ArrayDeque<>();for (int i = 0; i < n; ++i) {while (!stk.isEmpty() && prices[i] <= prices[stk.peek()]) {int l = stk.pop();ans[l] -= prices[i];}stk.push(i);}return ans;}
}

901. 股票价格跨度

https://leetcode.cn/problems/online-stock-span/
在这里插入图片描述

提示：

1 <= price <= 10^5
最多调用 next 方法 10^4 次

就是找每个位置的上一个更大的位置。

class StockSpanner {Deque<int[]> stk = new ArrayDeque();int i;public StockSpanner() {stk.push(new int[]{-1, 0x3f3f3f3f});i = -1;}public int next(int price) {while (price >= stk.peek()[1]) stk.pop();int res = ++i - stk.peek()[0];stk.push(new int[]{i, price});return res;}
}/*** Your StockSpanner object will be instantiated and called as such:* StockSpanner obj = new StockSpanner();* int param_1 = obj.next(price);*/

1019. 链表中的下一个更大节点

https://leetcode.cn/problems/next-greater-node-in-linked-list/description/
在这里插入图片描述

提示：
链表中节点数为 n
1 <= n <= 104
1 <= Node.val <= 10^9

先将链表转换成列表，再使用单调栈处理。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public int[] nextLargerNodes(ListNode head) {List<Integer> nums = new ArrayList<>();while (head != null) {nums.add(head.val);head = head.next;}int n = nums.size();int[] ans = new int[n];Deque<Integer> stk = new ArrayDeque<>();for (int i = 0; i < n; i++) {while (!stk.isEmpty() && nums.get(i) > nums.get(stk.peek())) {ans[stk.pop()] = nums.get(i);}stk.push(i);}return ans;}
}

84. 柱状图中最大的矩形

https://leetcode.cn/problems/largest-rectangle-in-histogram/description/

在这里插入图片描述

提示：

1 <= heights.length <=10^5
0 <= heights[i] <= 10^4

用单调栈计算出 l[] 和 r[]，这两个数组分别表示 i 左右两边第一个比 height[i] 更小的数。

class Solution {public int largestRectangleArea(int[] heights) {int n = heights.length, ans = 0;int[] l = new int[n], r = new int[n];Arrays.fill(l, -1);Arrays.fill(r, n);Deque<Integer> stk = new ArrayDeque<>();for (int i = 0; i < n; ++i) {while (!stk.isEmpty() && heights[i] < heights[stk.peek()]) {r[stk.pop()] = i;}if (!stk.isEmpty()) l[i] = stk.peek();stk.push(i);}for (int i = 0; i < n; ++i) {ans = Math.max(ans, heights[i] * (r[i] - l[i] - 1));}return ans;}
}