小猪学算法-单调栈

单调栈的使用场景相对来说比较少，非常具有代表性，一般遇到下一个最大的、下一个最小的、上一个最大的、上一个最小的问题优先考虑使用单调栈来解决。

单调栈就是栈里的数据递增或递减存放，也就是要做到有序，如果待入栈数据不符合栈里数据的有序性，则栈顶出栈，直到栈里数据有序，并将待入栈数据插入到栈顶。假如栈里的数据的顺序是从栈底到栈顶是递增的，代码如下：

输入一个数组 nums，请你返回一个等长的结果数组，结果数组中对应索引存储着下一个更大元素，如果没有更大的元素，就存 -1。

int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    // 存放答案的数组
    int[] res = new int[n];
    Stack<Integer> s = new Stack<>(); 
    // 倒着往栈里放
    for (int i = n - 1; i >= 0; i--) {
        // 判定个子高矮
        while (!s.isEmpty() && s.peek() <= nums[i]) {
            // 矮个起开，反正也被挡着了。。。
            s.pop();
        }
        // nums[i] 身后的更大元素
        res[i] = s.isEmpty() ? -1 : s.peek();
        s.push(nums[i]);
    }
    return res;
}

上述解答，最后的stack栈里还有啥数据？

尝试使用用例{2, 3, 1, 4, 3}进行验证时，stack中的数据是4-3-2，其中4最先入栈。而在构建这个stack的过程中我们巧妙的解决了问题。

同类问题

496. 下一个更大元素 I =》一个数组拆成两个数组

503. 下一个更大元素 II =》需要处理循环场景

739. 每日温度 =》 求的是距离，而不是具体的值

剑指 Offer II 038. 每日温度

901. 股票价格跨度 - 力扣（LeetCode）

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/online-stock-span
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果