单调栈

单调栈

适用范围: 当前元素左(右)第一个比其大或小的元素(位置)
作用: 作为缓冲机制, 存放之前遍历过的元素

当单调栈由栈顶元素至栈底元素是单调"递增"时: 求的是当前元素右边比其"大"的元素
当单调栈由栈顶元素至栈底元素是单调"递减"时: 求的是当前元素右边比其"小"的元素

例题1

739. 每日温度
给定一个整数数组 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:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        st = []
        ans = [0] * n
        for i in range(n):
            while st and temperatures[st[-1]] < temperatures[i]:
                ans[st[-1]] = i - st[-1]
                st.pop(-1)
            st.append(i)
        # while st:		(ans中的值均初始化为0)
        #     ans[st[-1]] = 0
        #     st.pop(-1)
        return ans

例题2

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] 是如上所述的 下一个更大元素 。

示例 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:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        n = len(nums1)
        ans = [-1] * n
        for index, num in enumerate(nums1):
            for i in range(nums2.index(num)+1,len(nums2)):
                if i >= len(nums2):
                    break
                else:
                    if num < nums2[i]:
                        ans[index] = nums2[i]
                        break
        return ans

代码 (单调栈法)

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        n1 = len(nums1)
        n2 = len(nums2)
        ans = [-1] * n1
        caches = [-1] * n2
        st = []
        for i in range(n2):
            while st and nums2[i] > nums2[st[-1]]:
                caches[st[-1]] = i
                st.pop(-1)
            st.append(i)
        for i, num in enumerate(nums1):
            if caches[nums2.index(num)]+1:
                ans[i] = nums2[caches[nums2.index(num)]]
        return ans