中等

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：

• 1 <= temperatures.length <= 105
• 30 <= temperatures[i] <= 100

单调栈的两种思路

写法一：从左到右，栈中记录「还没算出下一个更大元素」的那些数「的下标」

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        // 维护一个单调递减栈
        Deque<Integer> dq = new ArrayDeque<>();
        for(int i = 0; i < n; i++){
            while(!dq.isEmpty() && temperatures[dq.peekLast()] < temperatures[i]){
                int idx = dq.pollLast();
                res[idx] = i - idx;
            }
            dq.addLast(i);
        }
        return res;
    }
}

写法二：从右到左，栈中记录下一个更大元素的「候选项」

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        // 维护一个单调递减栈
        Deque<Integer> dq = new ArrayDeque<>();
        for(int i = n-1; i >= 0; i--){
            int t = temperatures[i];
            while(!dq.isEmpty() && t >= temperatures[dq.peekLast()]){
                dq.pollLast();
            }
            if(!dq.isEmpty()) // 如果栈为空，说明当前i比右边的值都大
                res[i] = dq.peekLast() - i;
            dq.addLast(i);
        }
        return res;
    }
}

困难

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：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：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

class Solution {
    // 找上一个更大元素，在找的过程中填坑
    public int trap(int[] height) {
        int n = height.length;
        int res = 0;
        Deque<Integer> dq = new ArrayDeque<>();
        for(int i = 0; i < n; i++){
            int h = height[i];
            while(!dq.isEmpty() && height[dq.peekLast()] <= height[i]){
                int bottomh = height[dq.pollLast()]; // 记录中间柱子的高度
                if(dq.isEmpty()) // 为空则退出，因为接雨水需要两根柱子
                    break;
                // 高度 = min(左右两边的柱子高度) - 当前柱子高度
                int dh = Math.min(height[dq.peekLast()], h) - bottomh;
                // 宽度 = 左右两边柱子的距离
                int dw = i - dq.peekLast() - 1;
                res += dw * dh;
            }
            dq.addLast(i);
        }
        return res;
    }
}

简单

给你一个数组 prices ，其中 prices[i] 是商店里第 i 件商品的价格。

商店里正在进行促销活动，如果你要买第 i 件商品，那么你可以得到与 prices[j] 相等的折扣，其中 j 是满足 j > i 且 prices[j] <= prices[i] 的 最小下标 ，如果没有满足条件的 j ，你将没有任何折扣。

请你返回一个数组，数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。

示例 1：

输入：prices = [8,4,6,2,3]
输出：[4,2,4,2,3]
解释：
商品 0 的价格为 price[0]=8 ，你将得到 prices[1]=4 的折扣，所以最终价格为 8 - 4 = 4 。
商品 1 的价格为 price[1]=4 ，你将得到 prices[3]=2 的折扣，所以最终价格为 4 - 2 = 2 。
商品 2 的价格为 price[2]=6 ，你将得到 prices[3]=2 的折扣，所以最终价格为 6 - 2 = 4 。
商品 3 和 4 都没有折扣。

示例 2：

输入：prices = [1,2,3,4,5]
输出：[1,2,3,4,5]
解释：在这个例子中，所有商品都没有折扣。

示例 3：

输入：prices = [10,1,1,6]
输出：[9,0,1,6]

提示：

• 1 <= prices.length <= 500
• 1 <= prices[i] <= 10^3

class Solution {
    public int[] finalPrices(int[] prices) {
        int n = prices.length;
        // 单增栈，找到比当前元素更小的下一个元素
        Deque<Integer> dq = new ArrayDeque<>();
        int[] res = new int[n];
        for(int i = 0; i < n; i++){
            while(!dq.isEmpty() && prices[dq.peekLast()] >= prices[i]){
                int idx = dq.pollLast(); // 需要弹出的元素，记录答案
                res[idx] = prices[idx] - prices[i];
            }
            dq.addLast(i);
        }
        // 最后栈中的元素都是没有折扣的（找不到下一个更小的元素的下标）
        while(!dq.isEmpty()){
            int idx = dq.pollLast();
            res[idx] = prices[idx];
        }
        return res;
    }
}

中等

设计一个算法收集某些股票的每日报价，并返回该股票当日价格的 跨度 。

当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。

• 例如，如果未来 7 天股票的价格是 [100,80,60,70,60,75,85]，那么股票跨度将是 [1,1,1,2,1,4,6] 。

实现 StockSpanner 类：

• StockSpanner() 初始化类对象。
• int next(int price) 给出今天的股价 price ，返回该股票当日价格的 跨度 。

示例：

输入：
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
输出：
[null, 1, 1, 1, 2, 1, 4, 6]

解释：
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // 返回 1
stockSpanner.next(80);  // 返回 1
stockSpanner.next(60);  // 返回 1
stockSpanner.next(70);  // 返回 2
stockSpanner.next(60);  // 返回 1
stockSpanner.next(75);  // 返回 4 ，因为截至今天的最后 4 个股价 (包括今天的股价 75) 都小于或等于今天的股价。
stockSpanner.next(85);  // 返回 6

提示：

• 1 <= price <= 105
• 最多调用 next 方法 104 次

class StockSpanner {
    /**
    股票价格小于或等于今天价格的最大连续日数
    寻找上一个更大的元素
     */
    Deque<int[]> dq; // price, i
    int i;
    public StockSpanner() {
        i = 0;
        dq = new ArrayDeque<>();
        dq.addLast(new int[]{Integer.MAX_VALUE, -1});
    }
    
    public int next(int price) {
        while(dq.size() > 1 && dq.peekLast()[0] <= price)
            dq.pollLast();
        int res = i - dq.peekLast()[1];
        dq.addLast(new int[]{price, i++});
        return res;
    }
}

中等

给定一个长度为 n 的链表 head

对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。

返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。

示例 1：

输入：head = [2,1,5]
输出：[5,5,0]

示例 2：

输入：head = [2,7,4,3,5]
输出：[7,0,5,5,0]

提示：

• 链表中节点数为 n
• 1 <= n <= 104
• 1 <= Node.val <= 109

class Solution {
    public int[] nextLargerNodes(ListNode head) {
        int n = getlen(head);
        int[] res = new int[n];
        Deque<int[]> dq = new ArrayDeque<>();// val, i
        ListNode p = head;
        int i = 0;
        while(p != null){
            while(!dq.isEmpty() && dq.peekLast()[0] < p.val){
                int[] q = dq.pollLast();
                res[q[1]] = p.val;
            }
            dq.addLast(new int[]{p.val, i++});
            p = p.next;
        }
        return res;
    }

    public int getlen(ListNode head){
        int len = 0;
        ListNode p = head;
        while(p != null){
            len += 1;
            p = p.next;
        }
        return len;
    }
}

简单

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：

输入：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：

输入：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 <= 1000
• 0 <= nums1[i], nums2[i] <= 104
• nums1和nums2中所有整数 互不相同
• nums1 中的所有整数同样出现在 nums2 中

class Solution {
    //  没有重复元素 
    // nums1 是 nums2 的子集。 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
    // 单调栈计算每个nums2的下一个更大元素，然后收集答案
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[] res = new int[n];
        Map<Integer, Integer> map = new HashMap<>();
        Deque<Integer> dq = new ArrayDeque<>();
        for(int x : nums2){
            while(!dq.isEmpty() && dq.peekLast() < x){
                map.put(dq.pollLast(), x);
            }
            dq.addLast(x);
        }
        for(int i = 0; i < n; i++){
            res[i] = map.getOrDefault(nums1[i], -1);
        }
        return res;
    }
}

中等

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

示例 1:

输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数； 
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

示例 2:

输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]

提示:

• 1 <= nums.length <= 104
• -109 <= nums[i] <= 109

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        Deque<Integer> dq = new ArrayDeque<>();
        for(int i = 0; i < n * 2; i++){
            while(!dq.isEmpty() && nums[i % n] > nums[dq.peekLast()]){
                res[dq.pollLast()] = nums[i % n];
            }
            dq.addLast(i % n);
        }
        return res;
    }
}

困难

给你一个下标从 0 开始的非负整数数组 nums 。对于 nums 中每一个整数，你必须找到对应元素的 第二大 整数。

如果 nums[j] 满足以下条件，那么我们称它为 nums[i] 的 第二大 整数：

• j > i
• nums[j] > nums[i]
• 恰好存在 一个 k 满足 i < k < j 且 nums[k] > nums[i] 。

如果不存在 nums[j] ，那么第二大整数为 -1 。

• 比方说，数组 [1, 2, 4, 3] 中，1 的第二大整数是 4 ，2 的第二大整数是 3 ，3 和 4 的第二大整数是 -1 。

请你返回一个整数数组 answer ，其中 answer[i]是 nums[i] 的第二大整数。

示例 1：

输入：nums = [2,4,0,9,6]
输出：[9,6,6,-1,-1]
解释：
下标为 0 处：2 的右边，4 是大于 2 的第一个整数，9 是第二个大于 2 的整数。
下标为 1 处：4 的右边，9 是大于 4 的第一个整数，6 是第二个大于 4 的整数。
下标为 2 处：0 的右边，9 是大于 0 的第一个整数，6 是第二个大于 0 的整数。
下标为 3 处：右边不存在大于 9 的整数，所以第二大整数为 -1 。
下标为 4 处：右边不存在大于 6 的整数，所以第二大整数为 -1 。
所以我们返回 [9,6,6,-1,-1] 。

示例 2：

输入：nums = [3,3]
输出：[-1,-1]
解释：
由于每个数右边都没有更大的数，所以我们返回 [-1,-1] 。

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109

class Solution {
    /**
    1. 需要两个数据结构，存储遍历过的数
        s 存储遍历过的数
        t 存储遍历过，且这个数在右侧发现了比他大的数
    2. 单调递减的栈来实现 s 和 t
     */
    public int[] secondGreaterElement(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        // 模拟两个单调递减的栈，栈中的元素是下标
        Deque<Integer> s = new ArrayDeque<>();
        Deque<Integer> t = new ArrayDeque<>();
        for(int i = 0; i < n; i++){
            // 循环中先判断t，再判断s（若先判断s，则s中可能有元素转移到t，不符合条件）
            // 弹出比当前值小的元素值（找到了第二大的元素）
            while(!t.isEmpty() && nums[t.peek()] < nums[i]){
                res[t.pop()] = nums[i];
            }
            // s是递减栈(元素值从大到小),如果直接push进t中大小顺序会发生变化
            // 将s中元素挪到t中也应该是递减的，因此需要辅助栈tmp来帮忙
            Deque<Integer> tmp = new ArrayDeque<>();
            while(!s.isEmpty() && nums[s.peek()] < nums[i]){
                tmp.push(s.pop());
            }
            while(!tmp.isEmpty()){
                t.push(tmp.pop());
            }
            s.push(i);
        }
        return res;
    }
}

中等

给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。

如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,4]
输出：false
解释：序列中不存在 132 模式的子序列。

示例 2：

输入：nums = [3,1,4,2]
输出：true
解释：序列中有 1 个 132 模式的子序列： [1, 4, 2] 。

示例 3：

输入：nums = [-1,3,2,0]
输出：true
解释：序列中有 3 个 132 模式的的子序列：[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。

提示：

• n == nums.length
• 1 <= n <= 2 * 105
• -109 <= nums[i] <= 109

class Solution {
    /** 1 4 2
        从后往前遍历，维护一个单减栈, 使用k记录所有出栈元素的最大值，k表示132结构中的2
        枚举 i, 遍历到i时，只要发现满足nums[i]<k，说明我们找到了符合条件的ijk
        为什么？
        对于 i 而言，后面有一个比其大的元素（满足 i < k 和 j > k 的条件
        满足 j > k 是因为 j将k淘汰。则一定有 i < j
     */
    public boolean find132pattern(int[] nums) {
        int n = nums.length, k = Integer.MIN_VALUE;
        Deque<Integer> dq = new ArrayDeque<>(); // 单减栈，维护下标
        for(int i = n-1; i >= 0; i--){
            int x = nums[i];
            if(x < k) return true;
            while(!dq.isEmpty() && nums[dq.peekLast()] < x){
                k = Math.max(k, nums[dq.pollLast()]);
            }
            dq.addLast(i);
        }
        return false;
    }
}

中等

给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。

我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。

所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。

请你返回「表现良好时间段」的最大长度。

示例 1：

输入：hours = [9,9,6,0,6,6,9]
输出：3
解释：最长的表现良好时间段是 [9,9,6]。

示例 2：

输入：hours = [6,6,6]
输出：0

提示：

• 1 <= hours.length <= 104
• 0 <= hours[i] <= 16

class Solution {
    /**
    1观察到题目中给出数组中的元素有且只有两种,分别是大于8和小于等于8,而具体的数值没有意义.
    所以简单起见,我们用1代表大于8的元素,用-1代表小于等于8的元素
    2现在题目变成了：「计算arr的最长子数组，其元素和大于0」
     */
    public int longestWPI(int[] hours) {
        int n = hours.length;
        int[] pre = new int[n+1];
        for(int i = 0; i < n; i++)
            pre[i+1] = pre[i] + (hours[i] > 8 ? 1 : -1);
        // 维护一个单调递减栈，思考哪些值可以作为最长子数组的左端点j
        // 假设s[j] < s[i]，s[j]在栈中，当前遍历到i
        // 由于从j 离后面的k更远，i不可能是最长子数组的左端点1
        Deque<Integer> dq = new ArrayDeque<>();
        for(int i = 0; i <= n; i++){
            if(dq.isEmpty() || pre[dq.peekLast()] > pre[i])
                dq.addLast(i);
        }
        int res = 0;
        for(int i = n; i >= 0; i--){
            while(!dq.isEmpty() && pre[dq.peekLast()] < pre[i]){
                res = Math.max(res, i - dq.pollLast());
            }
        }
        return res;
    }
}

中等

给你一个下标从 0 开始的整数数组 nums 。在一步操作中，移除所有满足 nums[i - 1] > nums[i] 的 nums[i] ，其中 0 < i < nums.length 。

重复执行步骤，直到 nums 变为 非递减 数组，返回所需执行的操作数。

示例 1：

输入：nums = [5,3,4,4,7,3,6,11,8,5,11]
输出：3
解释：执行下述几个步骤：
- 步骤 1 ：[5,3,4,4,7,3,6,11,8,5,11] 变为 [5,4,4,7,6,11,11]
- 步骤 2 ：[5,4,4,7,6,11,11] 变为 [5,4,7,11,11]
- 步骤 3 ：[5,4,7,11,11] 变为 [5,7,11,11]
[5,7,11,11] 是一个非递减数组，因此，返回 3 。

示例 2：

输入：nums = [4,5,7,7,13]
输出：0
解释：nums 已经是一个非递减数组，因此，返回 0 。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

class Solution {
    /**
    问题转换，元素x会被左边某个比他大的元素y给删除，
        我们需要计算在删除x之前，删除了多少个比y小的元素，从而算出删除x的时刻（第几步操作）
    答案可以转换成所有（能被删除的）元素被删除的时刻的最大值

    对于一串非降的序列，该序列的每个元素被删除的时刻都是单调递增的
    利用这一单调性，我们只需要存储这串非降序列的「最后一个元素」被删除的时刻。

    我们可以用一个单调递减栈存储元素及其被删除的时刻，当遇到一个不小于栈顶的元素 x 时，就不断弹出栈顶元素，并取弹出元素被删除时刻的最大值
     */
    public int totalSteps(int[] nums) {
        int res = 0;
        Deque<int[]> dq = new ArrayDeque<>();
        for(int num : nums){
            int maxT = 0;
            while(!dq.isEmpty() && dq.peekLast()[0] <= num){
                maxT = Math.max(maxT, dq.pollLast()[1]);
            }
            maxT = dq.isEmpty() ? 0 : maxT + 1;
            res = Math.max(res, maxT);
            dq.addLast(new int[]{num, maxT});
        }
        return res;
    }
}

困难

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

提示：

• 1 <= heights.length <=105
• 0 <= heights[i] <= 104

class Solution {
    public int largestRectangleArea(int[] heights) {
        int max = 0;
        Deque<Integer> dq = new ArrayDeque<>(); 
        // 维护一个单调递增栈，当 heights[deque.peekLast()] > heights[i]时
        // 说明以 deque.peekLast() 为高的矩形需要弹出了 宽就是 i 到 左边界(栈中下一个元素)的长度
        for(int i = 0; i < heights.length; i++){
            while(!dq.isEmpty() && heights[dq.peekLast()] > heights[i]){
                // 枚举以每个柱形为高度的最大矩形的面积
                int h = dq.pollLast();
                int left = dq.isEmpty() ? -1 : dq.peekLast(); // 空为-1 是方便计算区间[left, right]
                max = Math.max(max, (i - (left+1)) * heights[h]);
            }
            dq.addLast(i);
        }
        // 栈中剩余元素都是单调递增的，依次弹出
        // 左边界是栈中前一个元素，右边界是heights数组的长度
        while(!dq.isEmpty()){
            int h = dq.pollLast();
            int left = dq.isEmpty() ? -1 : dq.peekLast();
            max = Math.max(max, (heights.length - (left + 1)) * heights[h]);
        }
        return max;
    }
}