力扣-901.股票价格跨度 && 单调栈

题目描述

思路及实现

901.股票价格跨度

你别说，这题求的是当天的股票价格趋势，然后是要用之前的状态求解当前状态的，这何尝不是DP（逃

向前遍历

最容易想到的一种实现就是每天都往前遍历之前的股票价格，如果满足就加上，同时因为我们使用了数组days保存每天的股票价格的跨度，所以可以避免一定的重复遍历。

class StockSpanner:

    def __init__(self):
        self.prices = []  # 保存每天的股票价格
        self.days = []  # 保存今天股票价格的跨度

    def next(self, price: int) -> int:
        self.prices.append(price)
        p = len(self.days) - 1
        day = 1
        while p >= 0:
            if self.prices[p] <= price:
                day += self.days[p]  # 如果今天价格大于之前某一天，那么他也大于那一天股票价格大于的其他天的价格（if a > b and b > c then a > c），直接加上那一天的股票价格的跨度
                p -= self.days[p]  # 一定程度上避免重复遍历
            else:
                break
        self.days.append(day)
        return day

单调栈

（P.S. 可以先去看看下面496）
既然是要求下一个更大的元素，很容易就能想到用单调栈求解，为了省去不必要的麻烦，我们可以使用二元组来保存每一个数据（当天是从第一天起计的第几天和当天股票的价格）。

class StockSpanner:

    def __init__(self):
        self.a_stack = [(-1, math.inf)]
        self.i = -1

    def next(self, price: int) -> int:
        self.i += 1
        while price >= self.a_stack[-1][1]:  # 遇到栈中有比自己小的股票价格就将其出栈（保持栈单调）
            self.a_stack.pop()
        self.a_stack.append((self.i, price))  # 把当前的股票的情况入栈
        return self.i - self.a_stack[-2][0]  # 计算股票价格的跨度

如果不是很理解为什么把小于当前价格的元素出栈之后减去下一个天数返回的就是当天股票价格的跨度的话，那可以不保存第几天，而是保存股票价格趋势，这样的话也是可以的，而且好理解。

class StockSpanner:

    def __init__(self):
        self.a_stack = [(-1, math.inf)]

    def next(self, price: int) -> int:
        i = 1  # 股票价格趋势最少为一天
        while price >= self.a_stack[-1][1]:  # 遇到栈中有比自己小的股票价格就将其出栈（保持栈单调）
            i += self.a_stack.pop()[0]  # 加上出栈的股票价格天数
        self.a_stack.append((i, price))  # 把当前的股票的情况入栈
        return i

496.下一个更大元素 I

暴力遍历

看一眼题目就知道可以暴力遍历的啦，正向也行反向也行，下面的代码把nums2反转了，然后遍历rvs_nums2，再对其中每个数往前遍历，找第一个大于当前数的数（也就是题目所说的下一个更大元素），并记录到一个字典中，
因为我们最后是需要返回一个对应nums1中的数的顺序的数组的，且没有相同的数字，所以利用字典可以很方便地存储每个数的状态。

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        a_dict = {}
        rvs_nums2 = list(reversed(nums2))
        for i, num in enumerate(rvs_nums2):
            while i > 0:
                if rvs_nums2[i - 1] > num:  # 如果前边有更大的数
                    a_dict[num] = rvs_nums2[i - 1]  # 保存更大的数字为值到当前数字为键的字典的键值对中
                    break
                i -= 1
            if num not in a_dict:  # 找不到更大的数
                a_dict[num] = -1
        return [a_dict[num] for num in nums1]

单调栈

很喜欢力扣这题的官方题解评论区一位老哥说的话：

单调栈，用于解决NGE（Next Greater Element）问题，因所维护的栈中元素呈单调递增/递减，所以叫单调栈。
下面是解决这类题目的模板代码：

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        a_dict={}
        a_stack=[]
        for num in reversed(nums2):
            while a_stack and a_stack[-1] <= num:
                a_stack.pop()
            a_dict[num] = a_stack[-1] if a_stack else -1
            a_stack.append(num)
        return [a_dict[num] for num in nums1]

可以看到我们会把题目给的数组先反转一次再进行遍历，然后直到当前数不大于栈顶数或空栈为止，执行弹出（pop）操作。
这是因为如果当前数比栈顶数大的话，那么在这之后的数如果能以栈顶数作为下一个更大元素，那肯定也能以当前数作为下一个更大元素，且我们的数组是反转过的，也就是后来数的下标才离得更近。
找到结果之后，把当前数入栈。

503.下一个更大元素 II

既然已经解决了最基本的单调栈，现在让我们来看看变形：现在不止要看右边了，因为是循环数组，所以也要看左边了。
看到题目给的循环，大家是不是马上就想到：%运算符！确实，数据结构不也这么学了吗，超过数组下标的话对数组长度取余就回去了，没错，这里也是一个道理。
仔细想想，我们可以知道无论怎么循环，这题本质上就是两个给定的数组拼在一起的NGE问题罢了，然后可以得出以下代码：

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        a_list = [-1] * n
        a_stack = []
        for i in range(n * 2 - 1, -1, -1):
            while a_stack and a_stack[-1] <= nums[i % n]:
                a_stack.pop()
            if a_stack:
                a_list[i % n] = a_stack[-1]
            a_stack.append(nums[i % n])
        return a_list

---

希望本文章能够帮到您~