单调栈
739. 每日温度
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n=temperatures.length;
int[] ans=new int[n];
Deque<Integer> stack=new ArrayDeque<>();
for (int i=n-1; i>=0 ;i--) {
int temp = temperatures[i];
while(!stack.isEmpty() && temp >= temperatures[stack.peek()]) {
stack.pop();
}
if(!stack.isEmpty()) {
ans[i]=stack.peek()-i;
}
stack.push(i);
}
return ans;
}
}1475. 商品折扣后的最终价格
给你一个数组 prices ，其中 prices[i] 是商店里第 i 件商品的价格。
商店里正在进行促销活动，如果你要买第 i 件商品，那么你可以得到与 prices[j] 相等的折扣，其中 j 是满足 j > i 且 prices[j] <= prices[i] 的 最小下标 ，如果没有满足条件的 j ，你将没有任何折扣。
请你返回一个数组，数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。
class Solution {
public int[] finalPrices(int[] prices) {
int n=prices.length;
int[] ans=new int[n];
Deque<Integer> stack=new ArrayDeque<>();
for (int i=n-1; i>=0; i--) {
while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
stack.pop();
}
if (!stack.isEmpty()){
ans[i]=prices[i]-prices[stack.peek()];
} else {
ans[i] = prices[i];
}
stack.push(i);
}
return ans;
}
}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] 是如上所述的 下一个更大元素 。
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int n=nums1.length, m=nums2.length;
int[] ans=new int[n];
int[] tmp=new int[m];
Arrays.fill(tmp, -1);
Deque<Integer> stack=new ArrayDeque<>();
Map<Integer, Integer> pos=new HashMap<>();
for (int i=m-1; i>=0; i--) {
pos.put(nums2[i], i);
while(!stack.isEmpty() && nums2[i] > nums2[stack.peek()]) {
stack.pop();
}
if (!stack.isEmpty()) {
tmp[i] = stack.peek();
}
stack.push(i);
}
for (int i=0; i<n; i++) {
int p = pos.get(nums1[i]);
ans[i] = tmp[p] == -1 ? -1 : nums2[tmp[p]];
}
return ans;
}
}503. 下一个更大元素 II
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
class Solution {
public int[] nextGreaterElements(int[] nums) {
int n=nums.length;
int[] ans=new int[n];
Arrays.fill(ans, -1);
Deque<Integer> stack=new ArrayDeque<>();
for (int i=0; i<2*n; i++) {
int num=nums[i%n];
while (!stack.isEmpty() && num > nums[stack.peek()%n]) {
int j=stack.pop();
ans[j]=nums[i%n];
}
stack.push(i%n);
}
return ans;
}
}1019. 链表中的下一个更大节点
给定一个长度为 n 的链表 head
对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。
返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。
/**
* 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) {
int length=0;
ListNode tmp=head;
List<Integer> list = new ArrayList<>();
while(tmp!=null) {
list.add(tmp.val);
tmp=tmp.next;
length++;
}
int[] ans=new int[length];
Deque<Integer> stack=new ArrayDeque<>();
for (int i=0; i<length; i++) {
int num=list.get(i);
while(!stack.isEmpty() && num > list.get(stack.peek())) {
int j=stack.pop();
ans[j]=num;
}
stack.push(i);
}
return ans;
}
}962. 最大宽度坡
给定一个整数数组 A，坡是元组 (i, j)，其中 i < j 且 A[i] <= A[j]。这样的坡的宽度为 j - i。
找出 A 中的坡的最大宽度，如果不存在，返回 0 。
class Solution {
public int maxWidthRamp(int[] nums) {
int n=nums.length;
int ans=0;
Deque<Integer> stack=new ArrayDeque<>();
stack.push(0);
for (int i=1; i<n; i++) {
if (nums[i] < nums[stack.peek()]) {
stack.push(i);
}
}
for (int i=n-1; i>=0; i--) {
int num=nums[i];
while (!stack.isEmpty() && num >= nums[stack.peek()]) {
ans=Math.max(ans, i-stack.peek());
stack.pop();
}
}
return ans;
}
}853. 车队
在一条单行道上，有 n 辆车开往同一目的地。目的地是几英里以外的 target 。
给定两个整数数组 position 和 speed ，长度都是 n ，其中 position[i] 是第 i 辆车的位置， speed[i] 是第 i 辆车的速度(单位是英里/小时)。
一辆车永远不会超过前面的另一辆车，但它可以追上去，并以较慢车的速度在另一辆车旁边行驶。
车队 是指并排行驶的一辆或几辆汽车。车队的速度是车队中 最慢 的车的速度。
即便一辆车在 target 才赶上了一个车队，它们仍然会被视作是同一个车队。
返回到达目的地的车队数量 。
class Solution {
public int carFleet(int target, int[] position, int[] speed) {
int n=position.length;
double[] time=new double[target];
for(int i=0; i<n; i++) {
time[position[i]] = (target-position[i])*1.0/speed[i];
System.out.print(time[position[i]] + " ");
}
Deque<Double> stack=new ArrayDeque<>();
for (double t:time) {
if (t>0) {
while(!stack.isEmpty() && t>=stack.peek()) {
stack.pop();
}
stack.push(t);
}
}
return stack.size();
}
}901. 股票价格跨度
设计一个算法收集某些股票的每日报价，并返回该股票当日价格的 跨度 。
当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
例如，如果未来 7 天股票的价格是
[100,80,60,70,60,75,85]，那么股票跨度将是[1,1,1,2,1,4,6]。
实现 StockSpanner 类：
StockSpanner()初始化类对象。int next(int price)给出今天的股价price，返回该股票当日价格的 跨度 。
class StockSpanner {
private final Deque<int[]> stack = new ArrayDeque<>();
private int curDay = -1; // 第一个 next 调用算作第 0 天
public StockSpanner() {
stack.push(new int[]{-1, Integer.MAX_VALUE}); // 这样无需判断栈为空的情况
}
public int next(int price) {
while (price >= stack.peek()[1]) {
stack.pop(); // 栈顶数据后面不会再用到了，因为 price 更大
}
int ans = ++curDay - stack.peek()[0];
stack.push(new int[]{curDay, price});
return ans;
}
}1124. 表现良好的最长时间段
给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。
我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。
所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。
请你返回「表现良好时间段」的最大长度。
class Solution {
public int longestWPI(int[] hours) {
int n=hours.length;
int[] array=new int[n];
for (int i=0; i<n; i++) {
array[i] = hours[i] > 8 ? 1 : -1;
}
int maxLen=0;
int prefixSum=0;
Map<Integer,Integer> map=new HashMap<>();
map.put(0, -1);
for (int i=0;i<n;i++) {
prefixSum += array[i];
if (prefixSum > 0) {
maxLen = i + 1;
}
// 如果发现当前 prefixSum - 1 已经出现在 map 中，说明可以找到一个子数组，使其和大于 0，此时更新最大长度。
if (map.containsKey(prefixSum-1)) {
maxLen = Math.max(maxLen, i-map.get(prefixSum-1));
}
// 记录第一次出现的prefixSum的位置
if (!map.containsKey(prefixSum)) {
map.put(prefixSum, i);
}
}
return maxLen;
}
}矩形面积
84. 柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
class Solution {
public int largestRectangleArea(int[] heights) {
int n=heights.length;
int[] left=new int[n];
int[] right=new int[n];
Deque<Integer> stack=new ArrayDeque<>();
//单调递增栈
stack.push(0);
for (int i=0; i<n; i++) {
while(!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
stack.pop();
}
left[i]=stack.isEmpty() ? -1 : stack.peek();
stack.push(i);
}
stack.clear();
for (int i=n-1; i>=0; i--) {
while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
stack.pop();
}
right[i]=stack.isEmpty() ? n : stack.peek();
stack.push(i);
}
int ans=0;
for (int i=0; i<n; i++) {
ans=Math.max(ans, (right[i]-left[i]-1) * heights[i]);
}
return ans;
}
}